WALCOM: Algorithm and Computation

1. Front Matter

   PDF

2. Invited Talks

   1. Combinatorial Optimization with Noisy Inputs: How Can We Separate the Wheat from the Chaff?

      • Peter Widmayer

      Pages 1-1

   2. Approximability of Stable Matching Problems

      • Kazuo Iwama

      Pages 2-2

   3. On Three-Dimensional Graph Drawing and Embedding

      • Sue Whitesides

      Pages 3-4

3. Graph Algorithms I

   1. Bounding the Number of Reduced Trees, Cographs, and Series-Parallel Graphs by Compression

      • Takeaki Uno, Ryuhei Uehara, Shin-ichi Nakano

      Pages 5-16

   2. Generalized Above Guarantee Vertex Cover and r-Partization

      • R. Krithika, N. S. Narayanaswamy

      Pages 17-27

4. Computational Geometry

   1. Farthest Voronoi Diagrams under Travel Time Metrics

      • Sang Won Bae, Kyung-Yong Chwa

      Pages 28-39

   2. Tight Bound for Farthest-Color Voronoi Diagrams of Line Segments

      • Sang Won Bae

      Pages 40-51

   3. Range Aggregate Maximal Points in the Plane

      • Ananda Swarup Das, Prosenjit Gupta, Anil Kishore Kalavagattu, Jatin Agarwal, Kannan Srinathan, Kishore Kothapalli

      Pages 52-63

5. Approximation Algorithms

   1. Approximating the Multi-level Bottleneck Assignment Problem

      • Trivikram Dokka, Anastasia Kouvela, Frits C. R. Spieksma

      Pages 64-75

   2. Reoptimization of the Maximum Weighted P _k -Free Subgraph Problem under Vertex Insertion

      • Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos

      Pages 76-87

   3. Comparing and Aggregating Partial Orders with Kendall Tau Distances

      • Franz J. Brandenburg, Andreas Gleißner, Andreas Hofmeier

      Pages 88-99

6. Graph Algorithms II

   1. On the Round-Trip 1-Center and 1-Median Problems

      • Biing-Feng Wang, Jhih-Hong Ye, Pei-Jung Chen

      Pages 100-111

   2. Triangle-Free Outerplanar 3-Graphs Are Pairwise Compatibility Graphs

      • Sammi Abida Salma, Md. Saidur Rahman

      Pages 112-123

   3. On Relaxing the Constraints in Pairwise Compatibility Graphs

      • Tiziana Calamoneri, Rossella Petreschi, Blerina Sinaimeri

      Pages 124-135

7. Graph Drawing I

   1. Universal Line-Sets for Drawing Planar 3-Trees

      • Md. Iqbal Hossain, Debajyoti Mondal, Md. Saidur Rahman, Sammi Abida Salma

      Pages 136-147

   2. On the Hardness of Point-Set Embeddability

      • Stephane Durocher, Debajyoti Mondal

      Pages 148-159

8. String and Data Structures

   1. Linear Time Inference of Strings from Cover Arrays Using a Binary Alphabet

      • Tanaeem M. Moosa, Sumaiya Nazeen, M. Sohel Rahman, Rezwana Reaz

      Pages 160-172

   2. Fat Heaps without Regular Counters

      • Amr Elmasry, Jyrki Katajainen

      Pages 173-185

9. Graph Drawing II

   1. Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles

      • Martin Fink, Jan-Henrik Haunert, Tamara Mchedlidze, Joachim Spoerhase, Alexander Wolff

      Pages 186-197

This book constitutes the refereed proceedings of the 6th International Workshop on Algorithms and Computation, WALCOM 2012, held in Dhaka, Bangladesh, in February 2012. The 20 full papers presented together with 3 invited papers were carefully reviewed and selected from 50 submissions. The papers are grouped in topical sections on graph algorithms; computational geometry; approximation algorithms; graph drawing; string and data structures; and games and cryptography.

• computational complexity
• elliptic curve cryptography
• multidimensional assignment
• parameterized complexity
• perfect graphs

• Graph Drawing and Information Visualization Laboratory, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Bangladesh

  Md. Saidur Rahman

• , Faculty of Engineering, Department of Computer Science, Gunma University, Kiryu-Shi, Japan

  Shin-ichi Nakano

Policies and ethics