| 2009 | Choosability of P5-Free Graphs. | Petr A. Golovach, Pinar Heggernes |
| 2009 | Regular Expressions with Counting: Weak versus Strong Determinism. | Wouter Gelade, Marc Gyssens, Wim Martens |
| 2009 | Hyper-minimisation Made Efficient. | Pawel Gawrychowski, Artur Jez |
| 2009 | A By-Level Analysis of Multiplicative Exponential Linear Logic. | Marco Gaboardi, Luca Roversi, Luca Vercelli |
| 2009 | Future-Looking Logics on Data Words and Trees. | Diego Figueira, Luc Segoufin |
| 2009 | A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems. | Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier |
| 2009 | Admissible Strategies in Infinite Games over Graphs. | Marco Faella |
| 2009 | Stochastic Process Creation. | Javier Esparza |
| 2009 | Representing Groups on Graphs. | Sagarmoy Dutta, Piyush P. Kurur |
| 2009 | How to Use Spanning Trees to Navigate in Graphs. | Feodor F. Dragan, Yang Xiang |
| 2009 | The Communication Complexity of Non-signaling Distributions. | Julien Degorre, Marc Kaplan, Sophie Laplante, Jrmie Roland |
| 2009 | Parameterized Complexity Classes under Logical Reductions. | Anuj Dawar, Yuguo He |
| 2009 | Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants. | Paolo D'Arco, Alfredo De Santis, Anna Lisa Ferrara, Barbara Masucci |
| 2009 | Self-indexed Text Compression Using Straight-Line Programs. | Francisco Claude, Gonzalo Navarro |
| 2009 | Recent Advances in Population Protocols. | Ioannis Chatzigiannakis, Othon Michail, Paul G. Spirakis |
| 2009 | Stochastic Games with Finitary Objectives. | Krishnendu Chatterjee, Thomas A. Henzinger, Florian Horn |
| 2009 | Constructing Brambles. | Mathieu Chapelle, Frdric Mazoit, Ioan Todinca |
| 2009 | Synchronization of Regular Automata. | Didier Caucal |
| 2009 | The Synchronization Problem for Locally Strongly Transitive Automata. | Arturo Carpi, Flavio D'Alessandro |
| 2009 | DP-Complete Problems Derived from Extremal NP-Complete Properties. | Yi Cao, Joseph C. Culberson, Lorna Stewart |
| 2009 | A Dichotomy Theorem for Polynomial Evaluation. | Irne Briquel, Pascal Koiran |
| 2009 | Branching Programs for Tree Evaluation. | Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr |
| 2009 | Few Product Gates But Many Zeros. | Bernd Borchert, Pierre McKenzie, Klaus Reinhardt |
| 2009 | Balanced Paths in Colored Graphs. | Alessandro Bianco, Marco Faella, Fabio Mogavero, Aniello Murano |
| 2009 | Sampling Edge Covers in 3-Regular Graphs. | Ivona Bezkov, William A. Rummler |