| 2009 | 1-Bounded Space Algorithms for 2-Dimensional Bin Packing. Francis Y. L. Chin, Hing-Fung Ting, Yong Zhang |
| 2009 | A Certifying Algorithm for 3-Colorability of Daniel Bruce, Chính T. Hoàng, Joe Sawada |
| 2009 | A Combinatorial Algorithm for Horn Programs. R. Chandrasekaran, K. Subramani |
| 2009 | A Linear Vertex Kernel for Maximum Internal Spanning Tree. Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Stéphan Thomassé |
| 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 | A Proof of the Molecular Conjecture. Naoki Katoh |
| 2009 | A Self-stabilizing and Local Delaunay Graph Construction. Riko Jacob, Stephan Ritscher, Christian Scheideler, Stefan Schmid |
| 2009 | A Simple, Fast, and Compact Static Dictionary. Scott Schneider, Michael Spertus |
| 2009 | A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability. Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, Maxim Sviridenko |
| 2009 | Algorithmic Folding Complexity. Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Stefan Langerman, Ryuhei Uehara |
| 2009 | Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings Yingfei Dong, Ding-Zhu Du, Oscar H. Ibarra |
| 2009 | Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes. Jinhee Chun, Ryosei Kasai, Matias Korman, Takeshi Tokuyama |
| 2009 | An Improved Approximation Algorithm for the Traveling Tournament Problem. Daisuke Yamaguchi, Shinji Imahori, Ryuhei Miyashiro, Tomomi Matsui |
| 2009 | An Optimal Labeling for Node Connectivity. Tai-Hsin Hsu, Hsueh-I Lu |
| 2009 | Approximating Points by a Piecewise Linear Function: I. Danny Z. Chen, Haitao Wang |
| 2009 | Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers. Danny Z. Chen, Haitao Wang |
| 2009 | Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time. Zhou Xu, Liang Xu |
| 2009 | Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics. Minming Li |
| 2009 | Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity. Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, Chaitanya Swamy |
| 2009 | Bandwidth on AT-Free Graphs. Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, Saket Saurabh |
| 2009 | Bounds on Contention Management Algorithms. Johannes Schneider, Roger Wattenhofer |
| 2009 | Bubblesort and Juggling Sequences. Ronald L. Graham |
| 2009 | Complexity of Approximating the Vertex Centroid of a Polyhedron. Khaled M. Elbassioni, Hans Raj Tiwary |
| 2009 | Computational Complexity of Cast Puzzles. Chuzo Iwamoto, Kento Sasaki, Kenji Nishio, Kenichi Morita |
| 2009 | Computing Large Matchings in Planar Graphs with Fixed Minimum Degree. Robert Franke, Ignaz Rutter, Dorothea Wagner |
| 2009 | Computing Multidimensional Persistence. Gunnar E. Carlsson, Gurjeet Singh, Afra Zomorodian |
| 2009 | Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets. Sylvain Guillemot, Jesper Jansson, Wing-Kin Sung |
| 2009 | Computing the Map of Geometric Minimal Cuts. Jinhui Xu, Lei Xu, Evanthia Papadopoulou |
| 2009 | Conditional Hardness of Approximating Satisfiable Max 3CSP- Linqing Tang |
| 2009 | Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in Qian-Ping Gu, Hisao Tamaki |
| 2009 | Convex Drawings of Internally Triconnected Plane Graphs on Xiao Zhou, Takao Nishizeki |
| 2009 | Counting in the Presence of Memory Faults. Gerth Stølting Brodal, Allan Grønlund Jørgensen, Gabriel Moruz, Thomas Mølhave |
| 2009 | Covering a Graph with a Constrained Forest (Extended Abstract). Cristina Bazgan, Basile Couëtoux, Zsolt Tuza |
| 2009 | Crossing-Free Acyclic Hamiltonian Path Completion for Planar Tamara Mchedlidze, Antonios Symvonis |
| 2009 | Data Structures for Approximate Orthogonal Range Counting. Yakov Nekrich |
| 2009 | Data Structures for Range Median Queries. Gerth Stølting Brodal, Allan Grønlund Jørgensen |
| 2009 | Deletion without Rebalancing in Multiway Search Trees. Siddhartha Sen, Robert Endre Tarjan |
| 2009 | Distributed Scheduling of Parallel Hybrid Computations. Shivali Agarwal, Ankur Narang, R. K. Shyamasundar |
| 2009 | Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems. Kazumasa Okumoto, Takuro Fukunaga, Hiroshi Nagamochi |
| 2009 | Dynamic 3-Sided Planar Range Queries with Expected Doubly Logarithmic Time. Gerth Stølting Brodal, Alexis C. Kaporis, Spyros Sioutas, Konstantinos Tsakalidis, Kostas Tsichlas |
| 2009 | Editing Graphs into Disjoint Unions of Dense Clusters. Jiong Guo, Iyad A. Kanj, Christian Komusiewicz, Johannes Uhlmann |
| 2009 | Electric Routing and Concurrent Flow Cutting. Jonathan A. Kelner, Petar Maymounkov |
| 2009 | Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming. Tomoki Imada, Shunsuke Ota, Hiroshi Nagamochi, Tatsuya Akutsu |
| 2009 | Exact Algorithms for Dominating Clique Problems. Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos |
| 2009 | Exact Algorithms for Set Multicover and Multiset Multicover Problems. Qiang-Sheng Hua, Dongxiao Yu, Francis C. M. Lau, Yuexuan Wang |
| 2009 | Exact Algorithms for the Bottleneck Steiner Tree Problem. Sang Won Bae, Sunghee Choi, Chunseok Lee, Shin-ichi Tanigawa |
| 2009 | Exploration of Periodically Varying Graphs. Paola Flocchini, Bernard Mans, Nicola Santoro |
| 2009 | Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs. Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska |
| 2009 | Finding All Approximate Gapped Palindromes. Ping-Hui Hsu, Kuan-Yu Chen, Kun-Mao Chao |
| 2009 | Finding Fullerene Patches in Polynomial Time. Paul S. Bonsma, Felix Breuer |
| 2009 | Folding a Better Checkerboard. Erik D. Demaine, Martin L. Demaine, Goran Konjevod, Robert J. Lang |
| 2009 | Fréchet Distance Problems in Weighted Regions. Yam Ki Cheung, Ovidiu Daescu |
| 2009 | General Pseudo-random Generators from Weaker Models of Computation. George Karakostas |
| 2009 | Generalized Reduction to Compute Toric Ideals. Deepanjan Kesh, Shashank K. Mehta |
| 2009 | Geodesic Spanners on Polyhedral Surfaces. Sanjiv Kapoor, Xiang-Yang Li |
| 2009 | Geometric Minimum Diameter Minimum Cost Spanning Tree Problem. Dae-Young Seo, D. T. Lee, Tien-Ching Lin |
| 2009 | Good Programming in Transactional Memory. Raphael Eidenbenz, Roger Wattenhofer |
| 2009 | Graph Orientations with Set Connectivity Requirements. Takuro Fukunaga |
| 2009 | Hilbert's Thirteenth Problem and Circuit Complexity. Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen |
| 2009 | I/O and Space-Efficient Path Traversal in Planar Graphs. Craig Dillabaugh, Meng He, Anil Maheshwari, Norbert Zeh |
| 2009 | I/O-Efficient Contour Tree Simplification. Lars Arge, Morten Revsbæk |
| 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 | Inapproximability of Maximal Strip Recovery. Minghui Jiang |
| 2009 | Induced Packing of Odd Cycles in a Planar Graph. Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos |
| 2009 | Interval Stabbing Problems in Small Integer Ranges. Jens M. Schmidt |
| 2009 | Linear and Sublinear Time Algorithms for Basis of Abelian Groups. Li Chen, Bin Fu |
| 2009 | Locating an Obnoxious Line among Planar Objects. Danny Z. Chen, Haitao Wang |
| 2009 | Lower Bounds on Fast Searching. Donald Stanley, Boting Yang |
| 2009 | Maintaining Nets and Net Trees under Incremental Motion. Minkyoung Cho, David M. Mount, Eunhui Park |
| 2009 | Max-Coloring Paths: Tight Bounds and Extensions. Telikepalli Kavitha, Julián Mestre |
| 2009 | Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms. Laurent Bulteau, Guillaume Fertin, Irena Rusu |
| 2009 | Min-Energy Scheduling for Aligned Jobs in Accelerate Model. Weiwei Wu, Minming Li, Enhong Chen |
| 2009 | Minimum Covering with Travel Cost. Sándor P. Fekete, Joseph S. B. Mitchell, Christiane Schmidt |
| 2009 | Minimum Cycle Bases of Weighted Outerplanar Graphs. Tsung-Hao Liu, Hsueh-I Lu |
| 2009 | New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body. Adrian Dumitrescu, Csaba D. Tóth |
| 2009 | New Results on Simple Stochastic Games. Decheng Dai, Rong Ge |
| 2009 | Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement. Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Corentin Travers |
| 2009 | On Lower Bounds for Constant Width Arithmetic Circuits. Vikraman Arvind, Pushkar S. Joglekar, Srikanth Srinivasan |
| 2009 | On Partitioning a Graph into Two Connected Subgraphs. Daniël Paulusma, Johan M. M. van Rooij |
| 2009 | On Protein Structure Alignment under Distance Constraint. Shuai Cheng Li, Yen Kaow Ng |
| 2009 | On Shortest Disjoint Paths in Planar Graphs. Yusuke Kobayashi, Christian Sommer |
| 2009 | On the Advice Complexity of Online Problems. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královic, Richard Královic, Tobias Mömke |
| 2009 | On the Camera Placement Problem. Rudolf Fleischer, Yihui Wang |
| 2009 | On the Infinitesimal Rigidity of Bar-and-Slider Frameworks. Naoki Katoh, Shin-ichi Tanigawa |
| 2009 | On the Tightness of the Buhrman-Cleve-Wigderson Simulation. Shengyu Zhang |
| 2009 | Online Knapsack Problems with Limited Cuts. Xin Han, Kazuhisa Makino |
| 2009 | Online Maximum Directed Cut. Amotz Bar-Noy, Michael Lampis |
| 2009 | Online Sorted Range Reporting. Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, Alejandro López-Ortiz |
| 2009 | Online paging for flash memory devices. Annamária Kovács, Ulrich Meyer, Gabriel Moruz, Andrei Negoescu |
| 2009 | Optimal Randomized Algorithm for the Density Selection Problem. Tien-Ching Lin, D. T. Lee |
| 2009 | PTAS for Anna Adamaszek, Artur Czumaj, Andrzej Lingas |
| 2009 | Parameterized Complexity of Arc-Weighted Directed Steiner Problems. Jiong Guo, Rolf Niedermeier, Ondrej Suchý |
| 2009 | Parameterizing Cut Sets in a Graph by the Number of Their Components. Takehiro Ito, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos |
| 2009 | Pattern Matching for 321-Avoiding Permutations. Sylvain Guillemot, Stéphane Vialette |
| 2009 | Popular Matchings with Variable Job Capacities. Telikepalli Kavitha, Meghana Nasre |
| 2009 | Posi-modular Systems with Modulotone Requirements under Permutation Constraints. Toshimasa Ishii, Kazuhisa Makino |
| 2009 | Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm. Francisco Claude, Reza Dorrigiv, Stephane Durocher, Robert Fraser, Alejandro López-Ortiz, Alejandro Salinger |
| 2009 | Querying Two Boundary Points for Shortest Paths in a Polygonal Domain. Sang Won Bae, Yoshio Okamoto |
| 2009 | Random Generation and Enumeration of Bipartite Permutation Graphs. Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara |
| 2009 | Range Non-overlapping Indexing. Hagai Cohen, Ely Porat |
| 2009 | Reconstructing Numbers from Pairwise Function Values. Shiteng Chen, Zhiyi Huang, Sampath Kannan |
| 2009 | Reconstructing Polygons from Scanner Data. Therese Biedl, Stephane Durocher, Jack Snoeyink |
| 2009 | Route-Enabling Graph Orientation Problems. Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara |
| 2009 | SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks. Ping Xu, Xiang-Yang Li |
| 2009 | Shifting Strategy for Geometric Graphs without Geometry. Imran A. Pirwani |
| 2009 | Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria. Xi Chen, Shang-Hua Teng |
| 2009 | Step-Assembly with a Constant Number of Tile Types. Ján Manuch, Ladislav Stacho, Christine Stoll |
| 2009 | Strong Robustness of Randomized Rumor Spreading Protocols. Benjamin Doerr, Anna Huber, Ariel Levavi |
| 2009 | Succinct Greedy Geometric Routing in the Euclidean Plane. Michael T. Goodrich, Darren Strash |
| 2009 | Succinct Index for Dynamic Dictionary Matching. Wing-Kai Hon, Tak Wah Lam, Rahul Shah, Siu-Lung Tam, Jeffrey Scott Vitter |
| 2009 | The Complexity of Perfect Matching Problems on Dense Hypergraphs. Marek Karpinski, Andrzej Rucinski, Edyta Szymanska |
| 2009 | The Complexity of Solving Stochastic Games on Graphs. Daniel Andersson, Peter Bro Miltersen |
| 2009 | The Directed Hausdorff Distance between Imprecise Point Sets. Christian Knauer, Maarten Löffler, Marc Scherfenberg, Thomas Wolle |
| 2009 | The Fault-Tolerant Facility Allocation Problem. Shihong Xu, Hong Shen |
| 2009 | The Identity Correspondence Problem and Its Applications. Paul Bell, Igor Potapov |
| 2009 | The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract). Tomoyuki Yamakami |
| 2009 | Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks. Minming Li, Peng-Jun Wan, F. Frances Yao |
| 2009 | Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs. Marwan Al-Jubeh, Mashhood Ishaque, Kristóf Rédei, Diane L. Souvaine, Csaba D. Tóth |
| 2009 | Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract). Pei-Chi Huang, Hsin-Wen Wei, Yen-Chiu Chen, Ming-Yang Kao, Wei-Kuan Shih, Tsan-sheng Hsu |
| 2009 | Untangled Monotonic Chains and Adaptive Range Search. Diego Arroyuelo, Francisco Claude, Reza Dorrigiv, Stephane Durocher, Meng He, Alejandro López-Ortiz, J. Ian Munro, Patrick K. Nicholson, Alejandro Salinger, Matthew Skala |
| 2009 | Upward Star-Shaped Polyhedral Graphs. Seok-Hee Hong, Hiroshi Nagamochi |
| 2009 | Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries. Yoshitaka Nakao, Hiroshi Nagamochi |
| 2009 | Worst-Case and Smoothed Analysis of Bodo Manthey, Heiko Röglin |