WALCOM: Algorithms and Computation

1. Front Matter

   PDF

2. Invited Talks

   1. Mobility and Computations: Some Open Research Directions

      • Nicola Santoro

      Pages 1-3

   2. Adversarial Prediction: Lossless Predictors and Fractal Like Adversaries

      • Rina Panigrahy

      Pages 4-4

3. Computational Geometry

   1. A Novel Efficient Approach for Solving the Art Gallery Problem

      • Alexander Kröller, Mahdi Moeini, Christiane Schmidt

      Pages 5-16

   2. Fixed-Orientation Equilateral Triangle Matching of Point Sets

      • Jasine Babu, Ahmad Biniaz, Anil Maheshwari, Michiel Smid

      Pages 17-28

   3. Online Exploration and Triangulation in Orthogonal Polygonal Regions

      • Sándor P. Fekete, Sophia Rex, Christiane Schmidt

      Pages 29-40

   4. A Competitive Strategy for Distance-Aware Online Shape Allocation

      • Sándor P. Fekete, Nils Schweer, Jan-Marc Reinhardt

      Pages 41-52

   5. Base Location Problems for Base-Monotone Regions

      • Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi et al.

      Pages 53-64

   6. Counting Maximal Points in a Query Orthogonal Rectangle

      • Ananda Swarup Das, Prosenjit Gupta, Kannan Srinathan

      Pages 65-76

   7. Voronoi Game on Graphs

      • Sayan Bandyapadhyay, Aritra Banik, Sandip Das, Hirak Sarkar

      Pages 77-88

4. Approximation and Randomized Algorithms

   1. Approximation Schemes for Covering and Packing

      • Rom Aschner, Matthew J. Katz, Gila Morgenstern, Yelena Yuditsky

      Pages 89-100

   2. A Randomised Approximation Algorithm for the Hitting Set Problem

      • Mourad El Ouali, Helena Fohlin, Anand Srivastav

      Pages 101-113

   3. Exact and Approximation Algorithms for Densest k-Subgraph

      • Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos

      Pages 114-125

   4. Linear-Time Constant-Ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs

      • Christophe Crespelle, Philippe Gambette

      Pages 126-136

   5. Approximation Algorithms for the Partition Vertex Cover Problem

      • Suman Kalyan Bera, Shalmoli Gupta, Amit Kumar, Sambuddha Roy

      Pages 137-145

5. Parallel and Distributed Computing

   1. Daemon Conversions in Distributed Self-stabilizing Algorithms

      • Wayne Goddard, Pradip K. Srimani

      Pages 146-157

   2. Broadcasting in Conflict-Aware Multi-channel Networks

      • Francisco Claude, Reza Dorrigiv, Shahin Kamali, Alejandro López-Ortiz, Paweł Prałat, Jazmín Romero et al.

      Pages 158-169

   3. Shared-Memory Parallel Frontier-Based Search

      • Shogo Takeuchi, Jun Kawahara, Akihiro Kishimoto, Shin-ichi Minato

      Pages 170-181

6. Graph Algorithms

   1. Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching

      • Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin

      Pages 182-193

   2. Triangle-Partitioning Edges of Planar Graphs, Toroidal Graphs and k-Planar Graphs

      • Jiawei Gao, Ton Kloks, Sheung-Hung Poon

      Pages 194-205

This book constitutes the refereed proceedings of the 7th International Workshop on Algorithms and Computation, WALCOM 2013, held in Kharagpur, India, in February 2013. The 29 full papers presented were carefully reviewed and selected from 86 submissions. The papers are organized in topical sections on computational geometry, approximation and randomized algorithms, parallel and distributed computing, graph algorithms, complexity and bounds, and graph drawing.

• competitive analysis
• error correction
• linear programming
• parallelization
• space-filling curves
• algorithm analysis and problem complexity

• School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India

  Subir Kumar Ghosh

• Graduate School of Information Sciences (GSIS), Tohoku University, Sendai, Japan

  Takeshi Tokuyama

Policies and ethics