| 2009 | Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks. | Minming Li, Peng-Jun Wan, F. Frances Yao |
| 2009 | Minimum Cycle Bases of Weighted Outerplanar Graphs. | Tsung-Hao Liu, Hsueh-I Lu |
| 2009 | Optimal Randomized Algorithm for the Density Selection Problem. | Tien-Ching Lin, D. T. Lee |
| 2009 | On Protein Structure Alignment under Distance Constraint. | Shuai Cheng Li, Yen Kaow Ng |
| 2009 | Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics. | Minming Li |
| 2009 | Online paging for flash memory devices. | Annamria Kovcs, Ulrich Meyer, Gabriel Moruz, Andrei Negoescu |
| 2009 | On Shortest Disjoint Paths in Planar Graphs. | Yusuke Kobayashi, Christian Sommer |
| 2009 | The Directed Hausdorff Distance between Imprecise Point Sets. | Christian Knauer, Maarten Lffler, Marc Scherfenberg, Thomas Wolle |
| 2009 | Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model. | Jin Wook Kim, Siwon Choi, Joong Chae Na, Jeong Seop Sim |
| 2009 | Generalized Reduction to Compute Toric Ideals. | Deepanjan Kesh, Shashank K. Mehta |
| 2009 | Electric Routing and Concurrent Flow Cutting. | Jonathan A. Kelner, Petar Maymounkov |
| 2009 | Popular Matchings with Variable Job Capacities. | Telikepalli Kavitha, Meghana Nasre |
| 2009 | Max-Coloring Paths: Tight Bounds and Extensions. | Telikepalli Kavitha, Julin Mestre |
| 2009 | On the Infinitesimal Rigidity of Bar-and-Slider Frameworks. | Naoki Katoh, Shin-ichi Tanigawa |
| 2009 | A Proof of the Molecular Conjecture. | Naoki Katoh |
| 2009 | The Complexity of Perfect Matching Problems on Dense Hypergraphs. | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska |
| 2009 | General Pseudo-random Generators from Weaker Models of Computation. | George Karakostas |
| 2009 | Geodesic Spanners on Polyhedral Surfaces. | Sanjiv Kapoor, Xiang-Yang Li |
| 2009 | A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths. | Naoyuki Kamiyama, Naoki Katoh |
| 2009 | Inapproximability of Maximal Strip Recovery. | Minghui Jiang |
| 2009 | A Self-stabilizing and Local Delaunay Graph Construction. | Riko Jacob, Stephan Ritscher, Christian Scheideler, Stefan Schmid |
| 2009 | Computational Complexity of Cast Puzzles. | Chuzo Iwamoto, Kento Sasaki, Kenji Nishio, Kenichi Morita |
| 2009 | Route-Enabling Graph Orientation Problems. | Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara |
| 2009 | Parameterizing Cut Sets in a Graph by the Number of Their Components. | Takehiro Ito, Marcin Kaminski, Danil Paulusma, Dimitrios M. Thilikos |
| 2009 | Posi-modular Systems with Modulotone Requirements under Permutation Constraints. | Toshimasa Ishii, Kazuhisa Makino |