WALCOM: Algorithms and Computation: 5th International Workshop, WALCOM 2011, New Delhi, India, February 18-20, 2011, Proceedings (Lecture Notes in Computer Science, 6552)

Annotation 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 Front Matter....Pages - Geometry and Topology from Point Cloud Data....Pages 1-1 The Disjoint Paths Problem: Algorithm and Structure....Pages 2-7 The Physarum Computer....Pages 8-8 Maximum Betweenness Centrality: Approximability and Tractable Cases....Pages 9-20 Approximation Algorithms for Minimum Chain Vertex Deletion....Pages 21-32 Oblivious Buy-at-Bulk in Planar Graphs....Pages 33-44 The Complexity of Acyclic Subhypergraph Problems....Pages 45-56 Inapproximability of b -Matching in k -Uniform Hypergraphs....Pages 57-69 k -Level Crossing Minimization Is NP -Hard for Trees....Pages 70-76 Efficient Computation of Time-Dependent Centralities in Air Transportation Networks....Pages 77-88 Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices....Pages 89-97 Minimum Enclosing Circle of a Set of Fixed Points and a Mobile Point....Pages 98-109 Efficient Top- k Queries for Orthogonal Ranges....Pages 110-121 Range-Aggregate Queries Involving Geometric Aggregation Operations....Pages 122-133 Multi Cover of a Polygon Minimizing the Sum of Areas....Pages 134-145 On the Discrete Unit Disk Cover Problem....Pages 146-157 Clustering with Internal Connectedness....Pages 158-169 Hashed Patricia Trie: Efficient Longest Prefix Matching in Peer-to-Peer Systems....Pages 170-181 De Bruijn Sequences for the Binary Strings with Maximum Density....Pages 182-190 A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs....Pages 191-201 Counting Spanning Trees in Graphs Using Modular Decomposition....Pages 202-213 On Graceful Labelings of Trees....Pages 214-220 Minimum-Layer Drawings of Trees....Pages 221-232 Back Matter....Pages -