| 2009 | On Optimally Partitioning a Text to Improve Its Compression. | Paolo Ferragina, Igor Nitto, Rossano Venturini |
| 2009 | Untitled record | Yuval Emek |
| 2009 | Narrow-Shallow-Low-Light Trees with and without Steiner Points. | Michael Elkin, Shay Solomon |
| 2009 | Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs. | Khaled M. Elbassioni, Kazuhisa Makino, Imran Rauf |
| 2009 | Bipartite Graph Matchings in the Semi-streaming Model. | Sebastian Eggert, Lasse Kliemann, Anand Srivastav |
| 2009 | Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard. | Christoph Drr, Flavio Guiez, Martn Matamala |
| 2009 | Piercing Translates and Homothets of a Convex Body. | Adrian Dumitrescu, Minghui Jiang |
| 2009 | Preemptive Online Scheduling with Reordering. | Gyrgy Dsa, Leah Epstein |
| 2009 | Minimizing Movement: Fixed-Parameter Tractability. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Dniel Marx |
| 2009 | Algorithms Meet Art, Puzzles, and Magic. | Erik D. Demaine |
| 2009 | Accelerating Multi-modal Route Planning by Access-Nodes. | Daniel Delling, Thomas Pajor, Dorothea Wagner |
| 2009 | A Global-Optimization Algorithm for Mixed-Integer Nonlinear Programs Having Separable Non-convexity. | Claudia D'Ambrosio, Jon Lee, Andreas Wchter |
| 2009 | Optimality and Competitiveness of Exploring Polygons by Mobile Robots. | Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc |
| 2009 | On the Performance of Approximate Equilibria in Congestion Games. | George Christodoulou, Elias Koutsoupias, Paul G. Spirakis |
| 2009 | Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling. | Chandra Chekuri, Sungjin Im, Benjamin Moseley |
| 2009 | Improved Approximation Algorithms for Label Cover Problems. | Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff |
| 2009 | Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation. | Jakub Chaloupka |
| 2009 | Computing 3D Periodic Triangulations. | Manuel Caroli, Monique Teillaud |
| 2009 | Constructing Delaunay Triangulations along Space-Filling Curves. | Kevin Buchin |
| 2009 | Kernel Bounds for Disjoint Cycles and Disjoint Paths. | Hans L. Bodlaender, Stphan Thomass, Anders Yeo |
| 2009 | Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. | Markus Blser, Christian Hoffmann |
| 2009 | Counting Paths and Packings in Halves. | Andreas Bjrklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto |
| 2009 | Cauchy's Theorem for Orthogonal Polyhedra of Genus 0. | Therese Biedl, Burkay Gen |
| 2009 | Hash, Displace, and Compress. | Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger |
| 2009 | Bounded Budget Betweenness Centrality Game for Strategic Network Formations. | Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang, Jiajie Zhu |