WALCOM: Algorithms and Computation

1. Front Matter

   PDF

2. Invited Talks

   1. Geometry and Topology from Point Cloud Data

      • Tamal Krishna Dey

      Pages 1-1

   2. The Disjoint Paths Problem: Algorithm and Structure

      • Ken-ichi Kawarabayashi

      Pages 2-7

   3. The Physarum Computer

      • Kurt Mehlhorn

      Pages 8-8

3. Approximation Algorithms

   1. Maximum Betweenness Centrality: Approximability and Tractable Cases

      • Martin Fink, Joachim Spoerhase

      Pages 9-20

   2. Approximation Algorithms for Minimum Chain Vertex Deletion

      • Mrinal Kumar, Sounaka Mishra, N. Safina Devi, Saket Saurabh

      Pages 21-32

   3. Oblivious Buy-at-Bulk in Planar Graphs

      • Srivathsan Srinivasagopalan, Costas Busch, S. Sitharama Iyengar

      Pages 33-44

4. Hardness

   1. The Complexity of Acyclic Subhypergraph Problems

      • David Duris, Yann Strozecki

      Pages 45-56

   2. Inapproximability of b-Matching in k-Uniform Hypergraphs

      • Mourad El Ouali, Antje Fretwurst, Anand Srivastav

      Pages 57-69

   3. k-Level Crossing Minimization Is NP-Hard for Trees

      • Martin Harrigan, Patrick Healy

      Pages 70-76

5. Algorithm Engineering

   1. Efficient Computation of Time-Dependent Centralities in Air Transportation Networks

      • Annabell Berger, Matthias Müller-Hannemann, Steffen Rechner, Alexander Zock

      Pages 77-88

   2. Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices

      • Michael Schneider

      Pages 89-97

6. Computational Geometry

   1. Minimum Enclosing Circle of a Set of Fixed Points and a Mobile Point

      • Aritra Banik, Bhaswar B. Bhattacharya, Sandip Das

      Pages 98-109

   2. Efficient Top-k Queries for Orthogonal Ranges

      • Saladi Rahul, Prosenjit Gupta, Ravi Janardan, K. S. Rajan

      Pages 110-121

   3. Range-Aggregate Queries Involving Geometric Aggregation Operations

      • Saladi Rahul, Ananda Swarup Das, K. S. Rajan, Kannan Srinathan

      Pages 122-133

7. Approximation Algorithms

   1. Multi Cover of a Polygon Minimizing the Sum of Areas

      • A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz, Gila Morgenstern

      Pages 134-145

   2. On the Discrete Unit Disk Cover Problem

      • Gautam K. Das, Robert Fraser, Alejandro Lòpez-Ortiz, Bradford G. Nickerson

      Pages 146-157

   3. Clustering with Internal Connectedness

      • Neelima Gupta, Aditya Pancholi, Yogish Sabharwal

      Pages 158-169

8. String Algorithms

   1. Hashed Patricia Trie: Efficient Longest Prefix Matching in Peer-to-Peer Systems

      • Sebastian Kniesburges, Christian Scheideler

      Pages 170-181

   2. De Bruijn Sequences for the Binary Strings with Maximum Density

      • Joe Sawada, Brett Stevens, Aaron Williams

      Pages 182-190

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.

• approximation algorithms
• biconvex graphs
• complexity
• computational geometry
• data structures
• dynamic programming
• lattice reduction
• longest path problem
• moving points
• peer-to-peer systems
• planar graphs
• polynomial algorithm
• probabilistic methods
• shortest path
• tree drawing
• algorithm analysis and problem complexity

• Department of Architecture and Architectural Engineering, Kyoto University, Nishikyo-ku, Japan

  Naoki Katoh

• Department of Computer Science and Engineering, Hauz Khas, Indian Institute of Technology, New Delhi, India

  Amit Kumar

Policies and ethics