This book constitutes the refereed proceedings of the Third International Workshop on Algorithms and Computation, WALCOM 2009, held in Kolkata, India, in February 2009.
The 30 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 102 submissions. The papers feature original research in the areas of design and analysis of algorithms, computational geometry, graph drawing and graph algorithms. The papers are organized in topical sections on computational geometry, graph algorithms, complexity, graph drawing, approximation algorithms, and randomized algorithms.
Author(s): Jacob Fox, János Pach (auth.), Sandip Das, Ryuhei Uehara (eds.)
Series: Lecture Notes in Computer Science 5431 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 408
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Computer Communication Networks; Computer Graphics; Computational Biology/Bioinformatics
Front Matter....Pages -
A Separator Theorem for String Graphs and Its Applications....Pages 1-14
Foundations of Exact Rounding....Pages 15-31
Approximating Shortest Paths in Graphs....Pages 32-43
Line Transversals and Pinning Numbers....Pages 44-46
Algorithms for Computing Diffuse Reflection Paths in Polygons....Pages 47-58
Shortest Gently Descending Paths....Pages 59-70
All Farthest Neighbors in the Presence of Highways and Obstacles....Pages 71-82
Improved Algorithm for a Widest 1-Corner Corridor....Pages 83-92
Maximum Neighbour Voronoi Games....Pages 93-104
On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem....Pages 105-116
Colinear Coloring on Graphs....Pages 117-128
Recursive Generation of 5-Regular Planar Graphs....Pages 129-140
Efficient Enumeration of Ordered Trees with k Leaves (Extended Abstract)....Pages 141-150
Generating All Triangulations of Plane Graphs (Extended Abstract)....Pages 151-164
Recognition of Unigraphs through Superposition of Graphs (Extended Abstract)....Pages 165-176
Random Generation and Enumeration of Proper Interval Graphs....Pages 177-189
A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs....Pages 190-201
Minmax Tree Cover in the Euclidean Space....Pages 202-213
Network Design with Weighted Degree Constraints....Pages 214-225
Minimum Cuts of Simple Graphs in Almost Always Linear Time....Pages 226-237
The Generalized Stable Allocation Problem....Pages 238-249
Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings....Pages 250-261
Core and Conditional Core Path of Specified Length in Special Classes of Graphs....Pages 262-273
The Planar k-Means Problem is NP-Hard....Pages 274-285
On the Computational Complexity of Monotone Constraint Satisfaction Problems....Pages 286-297
Parameterized Complexity of Stabbing Rectangles and Squares in the Plane....Pages 298-309
Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O ( n log n ) Area (Extended Abstract)....Pages 310-321
Matched Drawability of Graph Pairs and of Graph Triples....Pages 322-333
An Improved Upward Planarity Testing Algorithm and Related Applications....Pages 334-344
Spherical-Rectangular Drawings....Pages 345-356
The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated....Pages 357-368
The Minimal Manhattan Network Problem in Three Dimensions....Pages 369-380
Shape Matching by Random Sampling....Pages 381-393
Object Caching for Queries and Updates....Pages 394-405
Back Matter....Pages -
