| 2009 | Convex Drawings of Internally Triconnected Plane Graphs on | Xiao Zhou, Takao Nishizeki |
| 2009 | On the Tightness of the Buhrman-Cleve-Wigderson Simulation. | Shengyu Zhang |
| 2009 | The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract). | Tomoyuki Yamakami |
| 2009 | An Improved Approximation Algorithm for the Traveling Tournament Problem. | Daisuke Yamaguchi, Shinji Imahori, Ryuhei Miyashiro, Tomomi Matsui |
| 2009 | Computing the Map of Geometric Minimal Cuts. | Jinhui Xu, Lei Xu, Evanthia Papadopoulou |
| 2009 | Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time. | Zhou Xu, Liang Xu |
| 2009 | The Fault-Tolerant Facility Allocation Problem. | Shihong Xu, Hong Shen |
| 2009 | SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks. | Ping Xu, Xiang-Yang Li |
| 2009 | Min-Energy Scheduling for Aligned Jobs in Accelerate Model. | Weiwei Wu, Minming Li, Enhong Chen |
| 2009 | Conditional Hardness of Approximating Satisfiable Max 3CSP- | Linqing Tang |
| 2009 | Lower Bounds on Fast Searching. | Donald Stanley, Boting Yang |
| 2009 | Geometric Minimum Diameter Minimum Cost Spanning Tree Problem. | Dae-Young Seo, D. T. Lee, Tien-Ching Lin |
| 2009 | Deletion without Rebalancing in Multiway Search Trees. | Siddhartha Sen, Robert Endre Tarjan |
| 2009 | Bounds on Contention Management Algorithms. | Johannes Schneider, Roger Wattenhofer |
| 2009 | A Simple, Fast, and Compact Static Dictionary. | Scott Schneider, Michael Spertus |
| 2009 | Interval Stabbing Problems in Small Integer Ranges. | Jens M. Schmidt |
| 2009 | Random Generation and Enumeration of Bipartite Permutation Graphs. | Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara |
| 2009 | Shifting Strategy for Geometric Graphs without Geometry. | Imran A. Pirwani |
| 2009 | On Partitioning a Graph into Two Connected Subgraphs. | Danil Paulusma, Johan M. M. van Rooij |
| 2009 | Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems. | Kazumasa Okumoto, Takuro Fukunaga, Hiroshi Nagamochi |
| 2009 | Data Structures for Approximate Orthogonal Range Counting. | Yakov Nekrich |
| 2009 | Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries. | Yoshitaka Nakao, Hiroshi Nagamochi |
| 2009 | Crossing-Free Acyclic Hamiltonian Path Completion for Planar | Tamara Mchedlidze, Antonios Symvonis |
| 2009 | Step-Assembly with a Constant Number of Tile Types. | Jn Manuch, Ladislav Stacho, Christine Stoll |
| 2009 | Worst-Case and Smoothed Analysis of | Bodo Manthey, Heiko Rglin |