| 2009 | 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. Piotr Berman, Marek Karpinski, Alexander Zelikovsky |
| 2009 | A Comparison of Performance Measures for Online Algorithms. Joan Boyar, Sandy Irani, Kim S. Larsen |
| 2009 | A Distribution-Sensitive Dictionary with Low Space Overhead. Prosenjit Bose, John Howat, Pat Morin |
| 2009 | A Pseudopolynomial Algorithm for Alexandrov's Theorem. Daniel Kane, Gregory N. Price, Erik D. Demaine |
| 2009 | A Scheme for Computing Minimum Covers within Simple Regions. Matthew J. Katz, Gila Morgenstern |
| 2009 | Algorithms Meet Art, Puzzles, and Magic. Erik D. Demaine |
| 2009 | Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings Frank K. H. A. Dehne, Marina L. Gavrilova, Jörg-Rüdiger Sack, Csaba D. Tóth |
| 2009 | An Improved SAT Algorithm in Terms of Formula Length. Jianer Chen, Yang Liu |
| 2009 | Approximating Transitive Reductions for Directed Networks. Piotr Berman, Bhaskar DasGupta, Marek Karpinski |
| 2009 | Approximation Algorithms for Buy-at-Bulk Geometric Network Design. Artur Czumaj, Jurek Czyzowicz, Leszek Gasieniec, Jesper Jansson, Andrzej Lingas, Pawel Zylinski |
| 2009 | Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments. Farzad Hassanzadeh, David Rappaport |
| 2009 | Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. Martin Knauer, Joachim Spoerhase |
| 2009 | Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees. Hiroaki Yamamoto, Daichi Takenouchi |
| 2009 | Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs. Chenyu Yan, Yang Xiang, Feodor F. Dragan |
| 2009 | Computing the Implicit Voronoi Diagram in Triple Precision. David L. Millman, Jack Snoeyink |
| 2009 | Connect the Dot: Computing Feed-Links with Minimum Dilation. Boris Aronov, Kevin Buchin, Maike Buchin, Marc J. van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira, Bettina Speckmann |
| 2009 | Delaunay Triangulation of Imprecise Points Simplified and Extended. Kevin Buchin, Maarten Löffler, Pat Morin, Wolfgang Mulzer |
| 2009 | Drawing Graphs with Right Angle Crossings. Walter Didimo, Peter Eades, Giuseppe Liotta |
| 2009 | Dynamic Graph Clustering Using Minimum-Cut Trees. Robert Görke, Tanja Hartmann, Dorothea Wagner |
| 2009 | Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms. Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos |
| 2009 | Efficient Construction of Near-Optimal Binary and Multiway Search Trees. Prosenjit Bose, Karim Douïeb |
| 2009 | Fault Tolerant External Memory Algorithms. Gerth Stølting Brodal, Allan Grønlund Jørgensen, Thomas Mølhave |
| 2009 | Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance. Reza Dorrigiv, Stephane Durocher, Arash Farzan, Robert Fraser, Alejandro López-Ortiz, J. Ian Munro, Alejandro Salinger, Matthew Skala |
| 2009 | Inspecting a Set of Strips Optimally. Tom Kamphans, Elmar Langetepe |
| 2009 | Integer Programming: Optimization and Evaluation Are Equivalent. James B. Orlin, Abraham P. Punnen, Andreas S. Schulz |
| 2009 | Minimal Locked Trees. Brad Ballinger, David Charlton, Erik D. Demaine, Martin L. Demaine, John Iacono, Ching-Hao Liu, Sheung-Hung Poon |
| 2009 | New Results on Visibility in Simple Polygons. Alexander Gilbers, Rolf Klein |
| 2009 | On Making Directed Graphs Transitive. Mathias Weller, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann |
| 2009 | On Reconfiguration of Disks in the Plane and Related Problems. Adrian Dumitrescu, Minghui Jiang |
| 2009 | On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem. Wenliang Du, David Eppstein, Michael T. Goodrich, George S. Lueker |
| 2009 | On the Power of the Semi-Separated Pair Decomposition. Mohammad Ali Abam, Paz Carmi, Mohammad Farshi, Michiel H. M. Smid |
| 2009 | Online Priority Steiner Tree Problems. Spyros Angelopoulos |
| 2009 | Online Square Packing. Sándor P. Fekete, Tom Kamphans, Nils Schweer |
| 2009 | Optimal Embedding into Star Metrics. David Eppstein, Kevin A. Wortman |
| 2009 | Orientation-Constrained Rectangular Layouts. David Eppstein, Elena Mumford |
| 2009 | Plane Graphs with Parity Constraints. Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Alexander Pilz, Günter Rote, Bettina Speckmann, Birgit Vogtenhuber |
| 2009 | Rank-Balanced Trees. Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan |
| 2009 | Rank-Sensitive Priority Queues. Brian C. Dean, Zachary H. Jones |
| 2009 | Reconfiguration of List Edge-Colorings in a Graph. Takehiro Ito, Marcin Kaminski, Erik D. Demaine |
| 2009 | Resolving Loads with Positive Interior Stresses. Günter Rote, André Schulz |
| 2009 | Shortest Path Problems on a Polyhedral Surface. Atlas F. Cook, Carola Wenk |
| 2009 | Skip-Splay: Toward Achieving the Unified Bound in the BST Model. Jonathan Derryberry, Daniel Dominic Sleator |
| 2009 | Straight-Line Rectangular Drawings of Clustered Graphs. Patrizio Angelini, Fabrizio Frati, Michael Kaufmann |
| 2009 | Streaming Embeddings with Slack. Christiane Lammersen, Anastasios Sidiropoulos, Christian Sohler |
| 2009 | Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing. Prosenjit Bose, Meng He, Anil Maheshwari, Pat Morin |
| 2009 | The David Eppstein, Emma S. Spiro |
| 2009 | The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs. Krishnam Raju Jampani, Anna Lubiw |
| 2009 | Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality. Lukasz Kowalik, Marcin Mucha |
| 2009 | Two for One: Tight Approximation of 2D Bin Packing. Klaus Jansen, Lars Prädel, Ulrich M. Schwarz |
| 2009 | Worst-Case Optimal Adaptive Prefix Coding. Travis Gagie, Yakov Nekrich |