| 2009 | 1-Local 17/12-Competitive Algorithm for Multicoloring Hexagonal Graphs. Rafal Witkowski |
| 2009 | A Local Distributed Algorithm to Approximate MST in Unit Disc Graphs. Krzysztof Krzywdzinski |
| 2009 | Alternating Weighted Automata. Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger |
| 2009 | Closure Operators for Order Structures. Ryszard Janicki, Dai Tri Man Le, Nadezhda Zubkova |
| 2009 | Combinatorial Queries and Updates on Partial Words. Adrian Diaconu, Florin Manea, Catalin Tiseanu |
| 2009 | Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity. Peter Damaschke, Azam Sheikh Muhammad |
| 2009 | Computing Role Assignments of Chordal Graphs. Pim van 't Hof, Daniël Paulusma, Johan M. M. van Rooij |
| 2009 | Correcting Sorted Sequences in a Single Hop Radio Network. Marcin Kik |
| 2009 | Decision Version of the Road Coloring Problem Is NP-Complete. Adam Roman |
| 2009 | Depletable Channels: Dynamics and Behaviour. Pietro Cenciarelli, Daniele Gorla, Ivano Salvo |
| 2009 | Directed Graphs of Entanglement Two. Erich Grädel, Lukasz Kaiser, Roman Rabinovich |
| 2009 | Earliest Query Answering for Deterministic Nested Word Automata. Olivier Gauwin, Joachim Niehren, Sophie Tison |
| 2009 | Energy Complexity and Depth of Threshold Circuits. Kei Uchizawa, Takao Nishizeki, Eiji Takimoto |
| 2009 | Equivalence of Deterministic Nested Word to Word Transducers. Slawomir Staworko, Grégoire Laurence, Aurélien Lemay, Joachim Niehren |
| 2009 | Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings Miroslaw Kutylowski, Witold Charatonik, Maciej Gebala |
| 2009 | How to Guard the Guards Themselves. Moti Yung |
| 2009 | Independence Results for John Case, Samuel E. Moelius |
| 2009 | Maintaining Arrays of Contiguous Objects. Michael A. Bender, Sándor P. Fekete, Tom Kamphans, Nils Schweer |
| 2009 | Martingales on Trees and the Empire Chromatic Number of Random Trees. Colin Cooper, Andrew R. A. McGrae, Michele Zito |
| 2009 | Multiway In-Place Merging. Viliam Geffert, Jozef Gajdos |
| 2009 | NP-Completeness of Sadish Sadasivam, Huaming Zhang |
| 2009 | Noise-Resilient Group Testing: Limitations and Constructions. Mahdi Cheraghchi |
| 2009 | On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs. Subhas Kumar Ghosh, Koushik Sinha |
| 2009 | On Random Betweenness Constraints. Andreas Goerdt |
| 2009 | Open Maps Bisimulations for Higher Dimensional Automata Models. Elena S. Oshevskaya |
| 2009 | Parametrized Regular Infinite Games and Higher-Order Pushdown Strategies. Paul Hänsch, Michaela Slaats, Wolfgang Thomas |
| 2009 | Reachability in Thomas Thierauf, Fabian Wagner |
| 2009 | Small Weakly Universal Turing Machines. Turlough Neary, Damien Woods |
| 2009 | Small-Space Analogues of Valiant's Classes. Meena Mahajan, B. V. Raghavendra Rao |
| 2009 | The Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi |
| 2009 | The Longest Haplotype Reconstruction Problem Revisited. Riccardo Dondi |
| 2009 | Three-Valued Abstractions of Markov Chains: Completeness for a Sizeable Fragment of PCTL. Michael Huth, Nir Piterman, Daniel Wagner |