| 2009 | Optimal Transitions for Targeted Protein Quantification: Best Conditioned Submatrix Selection. | Rastislav Srmek, Bernd Fischer, Elias Vicari, Peter Widmayer |
| 2009 | On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis. | Axel Simroth, Alexander Souza |
| 2009 | A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions. | Akiyoshi Shioura, Mutsunori Yagiura |
| 2009 | Directional Geometric Routing on Mobile Ad Hoc Networks. | Kazushige Sato, Takeshi Tokuyama |
| 2009 | Limits to List Decoding Random Codes. | Atri Rudra |
| 2009 | HITS Can Converge Slowly, but Not Too Slowly, in Score and Rank. | Enoch Peserico, Luca Pretto |
| 2009 | Bidding on Configurations in Internet Ad Auctions. | S. Muthukrishnan |
| 2009 | The Closest Pair Problem under the Hamming Metric. | Kerui Min, Ming-Yang Kao, Hong Zhu |
| 2009 | Crossing-Optimal Acyclic HP-Completion for Outerplanar | Tamara Mchedlidze, Antonios Symvonis |
| 2009 | Popular Matchings: Structure and Algorithms. | Eric McDermid, Robert W. Irving |
| 2009 | On the Generalised Character Compatibility Problem for Non-branching Character Trees. | Jn Manuch, Murray Patterson, Arvind Gupta |
| 2009 | Multiple Round Random Ball Placement: Power of Second Chance. | Xiang-Yang Li, Yajun Wang, Wangsen Feng |
| 2009 | Extracting Computational Entropy and Learning Noisy Linear Functions. | Chia-Jung Lee, Chi-Jen Lu, Shi-Chun Tsai |
| 2009 | Classification of a Class of Counting Problems Using Holographic Reductions. | Michael Kowalczyk |
| 2009 | Reconstruction of Interval Graphs. | Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara |
| 2009 | Finding a Level Ideal of a Poset. | Shuji Kijima, Toshio Nemoto |
| 2009 | Space Efficient Multi-dimensional Range Reporting. | Marek Karpinski, Yakov Nekrich |
| 2009 | An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates. | George Karakostas, Stavros G. Kolliopoulos, Jing Wang |
| 2009 | Convex Recoloring Revisited: Complexity and Exact Algorithms. | Iyad A. Kanj, Dieter Kratsch |
| 2009 | Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem. | Tomoko Izumi, Taisuke Izumi, Hirotaka Ono, Koichi Wada |
| 2009 | Hierarchies and Characterizations of Stateless Multicounter Machines. | Oscar H. Ibarra, mer Egecioglu |
| 2009 | Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone. | Pinar Heggernes, Federico Mancini, Charis Papadopoulos, R. Sritharan |
| 2009 | On the Hardness and Approximability of Planar Biconnectivity Augmentation. | Carsten Gutwenger, Petra Mutzel, Bernd Zey |
| 2009 | Separating NE from Some Nonuniform Nondeterministic Complexity Classes. | Bin Fu, Angsheng Li, Liyu Zhang |
| 2009 | On Smoothed Analysis of Quicksort and Hoare's Find. | Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi |