WALCOM: Algorithms and Computation

Name: WALCOM: Algorithms and Computation | 5th International Workshop, WALCOM 2011, New Delhi, India, February 18-20, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

5th International Workshop, WALCOM 2011, New Delhi, India, February 18-20, 2011, Proceedings

Naoki Katoh Amit Kumar(Herausgeber*in)

Springer (Verlag)

Erschienen am 10. Februar 2011

XI, 233 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-19094-0 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title Page
Preface
Organization
Table of Contents
Invited Talks
Geometry and Topology from Point Cloud Data
The Disjoint Paths Problem: Algorithm and Structure
Background
Results
When k (The Number of Terminals) Is Bounded
Approximation
Purely Combinatorial Results
The Physarum Computer
Approximation Algorithms
Maximum Betweenness Centrality: Approximability and Tractable Cases
Introduction
Approximation Algorithms
Tight Examples
APX-Completeness
A Polynomial-Time Algorithm for Trees
Concluding Remarks
Approximation Algorithms for Minimum Chain Vertex Deletion
Introduction
Notations and Known Results
Approximation Algorithms
3-Factor Approximation Algorithm
Second 3-Factor Approximation Algorithm
2-Factor Approximation Algorithm
Maximum Vertex Induced Chain Subgraph
Hardness Results
Conclusion and Further Directions
Oblivious Buy-at-Bulk in Planar Graphs
Introduction
Problem Statement
Contribution
Related Work
Definitions
Sparse Cover
Algorithm
Analysis
Conclusions
Hardness
The Complexity of Acyclic Subhypergraph Problems
Introduction
Definitions
Spanning Acyclic Subhypergraphs
NP-Completeness for , and -Acyclicity
Maximum Acyclic Subhypergraphs
A Method to Determine the Degree of Polynomial Relatively to a Subset of Its Variables
Application of the Method
NP-Complete Cases
Conclusion
Inapproximability of b-Matching in k-Uniform Hypergraphs
Introduction
The Maximum b-Matching Problem: Definition and Previous Work
Preliminaries and Definitions
The Reduction from Max-E3-Lin-q and Non-approximability
The Reduction
Proof of the Non-approximability
Proof of the Structure Theorem (Theorem 2)
Open Problems
k-Level Crossing Minimization Is NP-Hard for Trees
Introduction
2-Leveled Trees with One Level Fixed
k-Leveled Trees
Conclusions
References
Algorithm Engineering
Efficient Computation of Time-Dependent Centralities in Air Transportation Networks
Introduction
Time-Dependent Network Model
Centrality
Experiments
Conclusions and Future Work
References
Analysis of Gauss-Sieve for Solving theShortest Vector Problem in Lattices
Introduction
Preliminaries
Experiments
Sieving for Different Types of Lattices
New Algorithm Characteristics
Chronological Behaviour of Gauss Sieve
Gauss Sieving with Known Goal-Norm
Pre-reducing Lattices
Conclusion
Computational Geometry
Minimum Enclosing Circle of a Set of Fixed Points and a Mobile Point
Introduction
Characterization the Center Function
Properties of the Radius Function
C(S) =
C(S) =
Computation of the Center Function
Conclusions
Efficient Top-k Queries for Orthogonal Ranges
Introduction
Related Work
Formal Problem Statement
Dynamic Structure for Reporting Top-k Points in Arbitrary Order
Handling Insertions and Deletions
Reporting Top-k Points in Sorted Order
Solution for IR1
Solution for IRd, d2
Conclusions and Future Work
Range-Aggregate Queries Involving Geometric Aggregation Operations
Introduction
Our Contribution
Static Range-Aggregate Point Enclosure
One-Dimensional Scenario
Extension to Higher Dimensions (d 2)
Semi-dynamic Range-Aggregate Point Enclosure
One-Dimensional Scenario
Extending It to Higher Dimensions
1-d Range-Aggregate Segment Intersection
Static Solution
Semi-dynamic Solution
Range-Aggregate Orthogonal Segment Intersection
Range-Aggregate Orthogonal Segment Intersection with Distant Constraint
Approximation Algorithms
Multi Cover of a Polygon Minimizing the Sum of Areas
Introduction
Related Work
Our Results
k-Cover of Polygon
k-Cover of Points
k-Cover of Polygon
On the Discrete Unit Disk Cover Problem
Introduction
Our Results
Related Work
Preliminaries
Testing Feasibility
Discrete Unit Disk Cover Problem
Within Strip Problem
Outside Strip Point Cover Problem
Conclusion
References
Clustering with Internal Connectedness
Introduction
Problem Definition and Notation
Related Work
Our Results
Hardness of Approximation
An O(logn)-Approximation Algorithm
Reduction to the CSCP Problem
Approximating the CSCP Problem
String Algorithms
Hashed Patricia Trie: Efficient Longest Prefix Matching in Peer-to-Peer Systems
Introduction
Related Work
Our Contribution: Hashed Patricia Trie
Patricia Trie
Hashed Patricia Trie
Applications
Operations
PrefixSearch(x)
Insert(x)
Delete(x)
Complexity Analysis
Conclusion
De Bruijn Sequences for the Binary Strings with Maximum Density
Introduction
Background
Construction
Algorithm
Open Problems
Graph Algorithms
A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs
Introduction
Preliminaries
Biconvex Orderings and Monotone Paths
Ordering of Vertices
Monotonic Path
The Algorithm and Correctness
Some Constructs and Notations Used in the Algorithm
Algorithm
Proof of Correctness
Correctness Argument
Time Complexity
Conclusion and Further Work
Counting Spanning Trees in Graphs Using Modular Decomposition
Introduction
Preliminaries
The Main Idea and the Contraction Process
The Algorithm
Processing Basic Graphs
Counting Spanning Trees in Linear Time
Concluding Remarks
References
On Graceful Labelings of Trees
Introduction
Preliminaries
Graceful Labeling
Conclusion
Minimum-Layer Drawings of Trees
Introduction
Preliminaries
Root-Visible Drawings of Trees
Minimum-Layer Drawings
Conclusion
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken