| 2009 | A Complete Characterisation of the Linear Clique-Width of Path Powers. Pinar Heggernes, Daniel Meister, Charis Papadopoulos |
| 2009 | A Computational Proof of Complexity of Some Restricted Counting Problems. Jin-Yi Cai, Pinyan Lu, Mingji Xia |
| 2009 | A Fixed-Parameter Enumeration Algorithm for the Weighted FVS Problem. Jianxin Wang, Guohong Jiang |
| 2009 | A Quadratic Kernel for 3-Set Packing. Faisal N. Abu-Khzam |
| 2009 | A Simple Greedy Algorithm for the k-Disjoint Flow Problem. Maren Martens |
| 2009 | An Almost Totally Universal Tile Set. Grégory Lafitte, Michael Weiss |
| 2009 | An Observation on Non-Malleable Witness-Indistinguishability and Non-Malleable Zero-Knowledge. Zongyang Zhang, Zhenfu Cao, Rong Ma |
| 2009 | An Online Algorithm for Applying Reinforcement Learning to Handle Ambiguity in Spoken Dialogues. Fangju Wang, Kyle Swegles |
| 2009 | Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems. Binhai Zhu |
| 2009 | Approximation and Hardness Results for Label Cut and Related Problems. Peng Zhang, Jin-Yi Cai, Linqing Tang, Wenbo Zhao |
| 2009 | Behavioral and Logical Equivalence of Stochastic Kripke Models in General Measurable Spaces. Ernst-Erich Doberkat |
| 2009 | Best-Order Streaming Model. Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai |
| 2009 | Block-Graph Width. Maw-Shang Chang, Ling-Ju Hung, Ton Kloks, Sheng-Lung Peng |
| 2009 | Co-evolution and Information Signals in Biological Sequences. Alessandra Carbone, Linda Dib |
| 2009 | Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG. Ei Ando, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita |
| 2009 | Constraints, Graphs, Algebra, Logic, and Complexity. Moshe Y. Vardi |
| 2009 | Discovering Almost Any Hidden Motif from Multiple Sequences in Polynomial Time with Low Sample Complexity and High Success Probability. Bin Fu, Ming-Yang Kao, Lusheng Wang |
| 2009 | Distributed Systems and Their Environments. Matthew Hennessy |
| 2009 | Embedding the Diamond Lattice in the c.e. tt-Degrees with Superhigh Atoms. Douglas Cenzer, Johanna N. Y. Franklin, Jiang Liu, Guohua Wu |
| 2009 | Exact and Experimental Algorithms for a Huffman-Based Error Detecting Code. Paulo Eustáquio Duarte Pinto, Fábio Protti, Jayme Luiz Szwarcfiter |
| 2009 | Feasibility of Motion Planning on Directed Graphs. Zhilin Wu, Stéphane Grumbach |
| 2009 | Fixed-Parameter Algorithms for Graph-Modeled Date Clustering. Jiong Guo |
| 2009 | Greedy Local Search and Vertex Cover in Sparse Random Graphs. Carsten Witt |
| 2009 | High Minimal Pairs in the Enumeration Degrees. Andrea Sorbi, Guohua Wu, Yue Yang |
| 2009 | Improved Deterministic Algorithms for Weighted Matching and Packing Problems. Qilong Feng, Yang Liu, Songjian Lu, Jianxin Wang |
| 2009 | Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data. Michael Elberfeld, Ilka Schnoor, Till Tantau |
| 2009 | Kolmogorov Complexity and Combinatorial Methods in Communication Complexity. Marc Kaplan, Sophie Laplante |
| 2009 | Linear Kernel for Planar Connected Dominating Set. Daniel Lokshtanov, Matthias Mnich, Saket Saurabh |
| 2009 | Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments. Anke van Zuylen |
| 2009 | Minimizing AND-EXOR Expressions for Multiple-Valued Two-Input Logic Functions. Takaaki Mizuki, Hitoshi Tsubata, Takao Nishizeki |
| 2009 | Minimum Vertex Ranking Spanning Tree Problem on Permutation Graphs. Ruei-Yuan Chang, Guanling Lee, Sheng-Lung Peng |
| 2009 | Neural Computations That Support Long Mixed Sequences of Knowledge Acquisition Tasks. Leslie G. Valiant |
| 2009 | On Parameterized Exponential Time Complexity. Jianer Chen, Iyad A. Kanj, Ge Xia |
| 2009 | On Spanners of Geometric Graphs. Iyad A. Kanj |
| 2009 | On the Complexity of the Multiple Stack TSP, kSTSP. Sophie Toulouse, Roberto Wolfler Calvo |
| 2009 | On the Connection between Interval Size Functions and Path Counting. Evangelos Bampas, Andreas-Nikolas Göbel, Aris Pagourtzis, Aris Tentes |
| 2009 | On the Red/Blue Spanning Tree Problem. Sergey Bereg, Minghui Jiang, Boting Yang, Binhai Zhu |
| 2009 | On the Tractability of Maximal Strip Recovery. Lusheng Wang, Binhai Zhu |
| 2009 | Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. Jirí Fiala, Petr A. Golovach, Jan Kratochvíl |
| 2009 | Polynomial-Time Algorithm for Sorting by Generalized Translocations. Xiao Yin, Daming Zhu |
| 2009 | Preserving Privacy versus Data Retention. Markus Hinkelmann, Andreas Jakoby |
| 2009 | Quantitative Aspects of Speed-Up and Gap Phenomena. Klaus Ambos-Spies, Thorsten Kräling |
| 2009 | Searching Trees: An Essay. Henning Fernau, Daniel Raible |
| 2009 | Searching a Circular Corridor with Two Flashlights. Bo Jiang, Xuehou Tan |
| 2009 | Strong Positive Reducibilities. Andrea Sorbi |
| 2009 | Terminal Coalgebras for Measure-Polynomial Functors. Christoph Schubert |
| 2009 | The Extended Turing Model as Contextual Tool. S. Barry Cooper |
| 2009 | The Two-Guard Polygon Walk Problem. John Z. Zhang |
| 2009 | Theory and Applications of Models of Computation, 6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings Jianer Chen, S. Barry Cooper |
| 2009 | Undecidability of Cost-Bounded Reachability in Priced Probabilistic Timed Automata. Jasper Berendsen, Taolue Chen, David N. Jansen |