WALCOM: Algorithms and Computation

1. Front Matter

   PDF

2. Invited Contribution

   1. Encoding Data Structures

      • Rajeev Raman

      Pages 1-7

3. Approximation Algorithms

   1. Fast Algorithms for Constrained Graph Density Problems

      • Venkatesan Chakaravarthy, Neelima Gupta, Aditya Pancholi, Sambuddha Roy

      Pages 8-19

   2. The Directed Ring Loading with Penalty Cost

      • Li Guan, Jianping Li, Xuejie Zhang, Weidong Li

      Pages 20-31

   3. Edge-Colorings of Weighted Graphs

      • Yuji Obata, Takao Nishizeki

      Pages 32-43

   4. Unit Covering in Color-Spanning Set Model

      • Ehsan Emamjomeh-Zadeh, Mohammad Ghodsi, Hamid Homapour, Masoud Seddighin

      Pages 44-52

4. Data Structures and Algorithms

   1. Compact Encodings and Indexes for the Nearest Larger Neighbor Problem

      • Seungbum Jo, Rajeev Raman, Srinivasa Rao Satti

      Pages 53-64

   2. A Practical Succinct Data Structure for Tree-Like Graphs

      • Johannes Fischer, Daniel Peters

      Pages 65-76

   3. Forming Plurality at Minimum Cost

      • Wei-Yin Lin, Yen-Wei Wu, Hung-Lung Wang, Kun-Mao Chao

      Pages 77-88

   4. Approximate Distance Oracle in O(n²) Time and O(n) Space for Chordal Graphs

      • Gaurav Singh, N. S. Narayanaswamy, G. Ramakrishna

      Pages 89-100

5. Computational Geometry

   1. Straight-Path Queries in Trajectory Data

      • Mark de Berg, Ali D. Mehrabi

      Pages 101-112

   2. Folding a Paper Strip to Minimize Thickness

      • Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara et al.

      Pages 113-124

   3. An Almost Optimal Algorithm for Voronoi Diagrams of Non-disjoint Line Segments

      • Sang Won Bae

      Pages 125-136

6. Combinatorial Algorithms

   1. PTAS’s for Some Metric p-source Communication Spanning Tree Problems

      • Santiago V. Ravelo, Carlos E. Ferreira

      Pages 137-148

   2. Fault-Tolerant Gathering of Asynchronous Oblivious Mobile Robots under One-Axis Agreement

      • Subhash Bhagat, Sruti Gan Chaudhuri, Krishnendu Mukhopadhyaya

      Pages 149-160

   3. Enumerating Eulerian Trails via Hamiltonian Path Enumeration

      • Hiroyuki Hanada, Shuhei Denzumi, Yuma Inoue, Hiroshi Aoki, Norihito Yasuda, Shogo Takeuchi et al.

      Pages 161-174

7. Distributed and Online Algorithms

   1. The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Trees

      • Thim Strothmann

      Pages 175-186

   2. An Efficient Silent Self-Stabilizing Algorithm for 1-Maximal Matching in Anonymous Networks

      • Yuma Asada, Michiko Inoue

      Pages 187-198

   3. Dynamic Online Multiselection in Internal and External Memory

      • Jérémy Barbay, Ankur Gupta, Srinivasa Rao Satti, Jonathan Sorenson

      Pages 199-209

   4. Competitive Analysis for Multi-objective Online Algorithms

      • Morten Tiedemann, Jonas Ide, Anita Schöbel

      Pages 210-221

This book constitutes the thoroughly refereed conference proceedings of the 9th International Workshop on Algorithms and Computation, WALCOM 2015, held in Dhaka, Bangladesh, in February 2015. The 26 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 85 submissions. The papers are organized in topical sections on approximation algorithms, data structures and algorithms, computational geometry, combinatorial algorithms, distributed and online algorithms, graph drawing and algorithms, combinatorial problems and complexity, and graph enumeration and algorithms.

• approximation algorithms
• combinatorial algorithms
• combinatorial optimization
• computational complexity
• computational geometry
• data structures
• distributed algorithms
• graph algorithms
• graph drawing
• network optimization
• online algorithms
• parameterized complexity
• recursion
• stringology
• algorithm analysis and problem complexity

• Department of CSE, BUET, Dhaka, Bangladesh

  M. Sohel Rahman

• The Advanced Algorithms Research Laboratory, The University of Electro-Communications, Chofu, Japan

  Etsuji Tomita

Policies and ethics