List of Accepted Papers, WADS 2009

Acceptance Rate: 39%. The final paper and the signed copyright form are due on May 11, 2009. (Click HERE to submit your final paper.)

• Piotr Berman, Bhaskar DasGupta and Marek Karpinski. Approximating Transitive Reductions for Directed Networks
• Adrian Dumitrescu and Minghui Jiang. On reconfiguration of disks in the plane and related problems
• Bourgeois Nicolas, Bruno Escoffier and Vangelis Paschos. Efficient approximation of combinatorial problems by moderately exponential algorithms
• Atlas F. Cook IV and Carola Wenk. Shortest Path Problems on a Polyhedral Surface
• Joan Boyar, Sandy Irani and Kim S. Larsen. A Comparison of Performance Measures for Online Algorithms
• Artur Czumaj, Jurek Czyzowicz, Leszek Gasieniec, Jesper Jansson, Andrzej Lingas and Pawe? ?yli?ski. Approximation Algorithms for Buy-at-Bulk Geometric Network Design
• Travis Gagie and Yakov Nekrich. Worst-Case Optimal Adaptive Prefix Coding
• Farzad Hassanzadeh and David Rappaport. Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments
• Tom Kamphans and Elmar Langetepe. Inspecting a Set of Strips Optimally
• Mathias Weller, Christian Komusiewicz, Rolf Niedermeier and Johannes Uhlmann. On Making Directed Graphs Transitive
• David Eppstein and Elena Mumford. Orientation-Constrained Rectangular Layouts
• Wenliang Du, David Eppstein, Michael Goodrich and George Lueker. On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
• David Eppstein and Emma S. Spiro. The h-index of a graph and its application to dynamic subgraph statistics
• Sandor Fekete, Tom Kamphans and Nils Schweer. Online Square Packing
• Walter Didimo, Peter Eades and Giuseppe Liotta. Drawing Graphs with Right Angle Crossings
• Chenyu Yan, Yang Xiang and Feodor Dragan. Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs
• David Eppstein and Kevin Wortman. Optimal embedding into star metrics
• Takehiro Ito, Marcin Kaminski and Erik D. Demaine. Reconfiguration of List Edge-Colorings in a Graph
• Christiane Lammersen, Anastasios Sidiropoulos and Christian Sohler. Streaming Embeddings with Slack
• Mohammad Ali Abam, Paz Carmi, Mohammad Farshi and Michiel Smid. On the Power of the Semi-Separated Pair Decomposition
• Karim Douïeb and Prosenjit Bose. Efficient Construction of Near-Optimal Binary and Multiway Search Trees
• Krishnam Raju Jampani and Anna Lubiw. The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs
• Prosenjit Bose, John Howat and Pat Morin. A Distribution-Sensitive Dictionary with Low Space Overhead
• Günter Rote and André Schulz. Resolving Loads with Positive Interior Stresses
• Prosenjit Bose, Meng He, Anil Maheshwari and Pat Morin. Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Klaus Jansen, Lars Prädel and Ulrich M. Schwarz. Two for One: Tight approximation of 2D Bin Packing
• Matthew J. Katz and Gila Morgenstern. A Scheme for Computing Minimum Covers within Simple Regions
• Allan Grønlund Jørgensen, Gerth Stølting Brodal and Thomas Mølhave. Fault Tolerant External Memory Algorithms
• Robert Görke, Tanja Hartmann and Dorothea Wagner. Dynamic Graph Clustering Using Minimum-Cut Trees
• Alexander Gilbers and Rolf Klein. New Results on Visibility in Simple Polygons
• Lukasz Kowalik and Marcin Mucha. Two approximation algorithms for ATSP with strengthened triangle inequality
• Hiroaki Yamamoto and Daichi Takenouchi. Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees
• Jonathan Derryberry and Daniel Sleator. Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Piotr Berman, Marek Karpinski and Alex Zelikovsky. 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
• Brian Dean and Zachary Jones. Rank-Sensitive Priority Queues
• Kevin Buchin, Maarten Löffler, Pat Morin and Wolfgang Mulzer. Delaunay Triangulation of Imprecise Points Simplified and Extended
• Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Alexander Pilz, Guenter Rote, Bettina Speckmann and Birgit Vogtenhuber. Plane Graphs with Parity Constraints
• Martin Knauer and Joachim Spoerhase. Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Patrizio Angelini, Fabrizio Frati and Michael Kaufmann. Straight-Line Rectangular Drawings of Clustered Graphs
• Brad Ballinger, David Charlton, Erik D. Demaine, Martin L. Demaine, John Iacono, Ching-Hao Liu and Sheung-Hung Poon. Minimal Locked Trees
• Boris Aronov, Kevin Buchin, Maike Buchin, Marc van Kreveld, Maarten Löffler, Jun Luo, Rodrigo Silveira and Bettina Speckmann. Connect the Dot: Computing Feed-links with Minimum Dilation
• Spyros Angelopoulos. Online Priority Steiner Tree Problems
• David L. Millman and Jack Snoeyink. Computing the implicit Voronoi diagram in triple precision
• Reza Dorrigiv, Stephane Durocher, Arash Farzan, Robert Fraser, Alejandro Lopez-Ortiz, J. Ian Munro, Alejandro Salinger and Matthew Skala. Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance
• Daniel Kane, Gregory N. Price and Erik D. Demaine. A pseudopolynomial algorithm for Alexandrov's Theorem
• Jianer Chen and Yang Liu. An Improved Algorithm for the General Satisfiability Problem
• Nadia Benbernou, Prosenjit Bose, David Bremner, Erik Demaine, Martin Demaine, Ferran Hurtado, Vera Sacristan and Perouz Taskakian. Efficient Reconfiguration of Pivoting Tiles
• Andreas S. Schulz, James Orlin and Abraham Punnen. Integer Programming: Optimization and Evaluation are Equivalent
• Bernhard Haeupler, Siddhartha Sen and Robert E. Tarjan. Balanced Trees Simplified