Walcom: Algorithms and Computation: Third International Workshop, Walcom 2009, Kolkata, India, February 18-20, 2009, Proceedings

ISBN-13: 9783642002014 / Angielski / Miękka / 2009 / 424 str.

Sandip Das

Opis

Welcome to the third annualWorkshopon Algorithms and Computation (WAL- COM 2009). The workshop provided a forum for researchers working in al- rithms and theory of computation from all over the world. This volume contains the papers presented at WALCOM 2009 held during February 18-20, 2009 at the Indian Statistical Institute, Kolkata, India. The scienti?c program of WALCOM 2009 included 30 contributed papers selected throughaveryhighqualityrefereeingprocessfrom102submissionswithauthors from 30 countries. In addition, there were four invited talks delivered by Otfried Cheong of KAIST, Korea, Janos Pach of Courant Institute, NY, USA, Sandeep SenofIndianInstitute ofTechnology, NewDelhi, IndiaandCheeYapofCourant Institute, NY, USA, who are all eminent and well-known researchers. As editors of these proceedings, we would like to thank all the authors who showed interest in WALCOM 2009. The reputation of a conference is enhanced by its Program Committee and the invited talks. We were able to get highly respected researchers to serve on our Program Committee. We are very much indebted to all members of the Program Committee who did excellent work in helping us to ?nalize the technical program. We also thank all external referees without whose help it would not have been possible to evaluate so many cont- butions in so little time. We thank the invited speakers for presenting their talks on current research areas of theoretical computer science.

Spis treści

Invited Talks.- A Separator Theorem for String Graphs and Its Applications.- Foundations of Exact Rounding.- Approximating Shortest Paths in Graphs.- Line Transversals and Pinning Numbers.- Computational Geometry.- Algorithms for Computing Diffuse Reflection Paths in Polygons.- Shortest Gently Descending Paths.- All Farthest Neighbors in the Presence of Highways and Obstacles.- Improved Algorithm for a Widest 1-Corner Corridor.- Maximum Neighbour Voronoi Games.- On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem.- Graph Algorithms.- Colinear Coloring on Graphs.- Recursive Generation of 5-Regular Planar Graphs.- Efficient Enumeration of Ordered Trees with k Leaves (Extended Abstract).- Generating All Triangulations of Plane Graphs (Extended Abstract).- Recognition of Unigraphs through Superposition of Graphs (Extended Abstract).- Random Generation and Enumeration of Proper Interval Graphs.- A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs.- Minmax Tree Cover in the Euclidean Space.- Network Design with Weighted Degree Constraints.- Minimum Cuts of Simple Graphs in Almost Always Linear Time.- The Generalized Stable Allocation Problem.- Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings.- Core and Conditional Core Path of Specified Length in Special Classes of Graphs.- Complexity.- The Planar k-Means Problem is NP-Hard.- On the Computational Complexity of Monotone Constraint Satisfaction Problems.- Parameterized Complexity of Stabbing Rectangles and Squares in the Plane.- Graph Drawing.- Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n logn) Area (Extended Abstract).- Matched Drawability of Graph Pairs and of Graph Triples.- An Improved Upward Planarity Testing Algorithm and Related Applications.- Spherical-Rectangular Drawings.- Approximation Algorithms.- The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated.- The Minimal Manhattan Network Problem in Three Dimensions.- Randomized Algorithms.- Shape Matching by Random Sampling.- Object Caching for Queries and Updates.

Blurb

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.