WALCOM: Algorithms and Computation
5th International Workshop, WALCOM 2011, New Delhi, India, February 18-20, 2011, Proceedings
Published on 10. February 2011
XI, 233 pages
978-3-642-19094-0 (ISBN)
Description
This book constitutes the proceedings of the 5th International Workshop on Algorithms and Computation, WALCOM 2011, held in New Delhi, India, in February 2011.
The 20 papers presented in this volume were carefully reviewed and selected from 57 submissions. The papers are grouped in topical sections on approximation algorithms, hardness, algorithm engineering, computational geometry, string algorithms, and graph algorithms.
More details
Other editions
Additional editions
Naoki Katoh | Amit Kumar
WALCOM: Algorithms and Computation
5th International Workshop, WALCOM 2011, New Delhi, India, February 18-20, 2011, Proceedings
Book
02/2011
1st Edition
Springer
€53.49
Shipment within 5-7 days
Content
- 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
