| 2005 | (Non)-Approximability for the Multi-criteria Eric Angel, Evripidis Bampis, Laurent Gourvès, Jérôme Monnot |
| 2005 | A Faster and Simpler 2-Approximation Algorithm for Block Sorting. Wolfgang W. Bein, Lawrence L. Larmore, Linda Morales, Ivan Hal Sudborough |
| 2005 | A New Linearizing Restriction in the Pattern Matching Problem. Yo-Sub Han, Derick Wood |
| 2005 | A Self-dependency Constraint in the Simply Typed Lambda Calculus. Aleksy Schubert |
| 2005 | A Simple and Fast Min-cut Algorithm. Michael Brinkmeier |
| 2005 | A Type System for Computationally Secure Information Flow. Peeter Laud, Varmo Vene |
| 2005 | Adaptive Zooming in Point Set Labeling. Sheung-Hung Poon, Chan-Su Shin |
| 2005 | Algorithms for Graphs Embeddable with Few Crossings Per Edge. Alexander Grigoriev, Hans L. Bodlaender |
| 2005 | Almost Optimal Explicit Selectors. Bogdan S. Chlebus, Dariusz R. Kowalski |
| 2005 | An Explicit Solution to Post's Problem over the Reals. Klaus Meer, Martin Ziegler |
| 2005 | An Improved Approximation Algorithm for TSP with Distances One and Two. Markus Bläser, L. Shankar Ram |
| 2005 | Approximation Results for the Weighted P Jérôme Monnot, Sophie Toulouse |
| 2005 | Average-Case Non-approximability of Optimisation Problems. Birgit Schelm |
| 2005 | Biautomatic Semigroups. Michael Hoffmann, Richard M. Thomas |
| 2005 | Bounds on the Power of Constant-Depth Quantum Circuits. Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang |
| 2005 | Clique-Width for Four-Vertex Forbidden Subgraphs. Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, Vadim V. Lozin |
| 2005 | Collapsing Recursive Oracles for Relativized Polynomial Hierarchies. Tomoyuki Yamakami |
| 2005 | Completeness and Compactness of Quantitative Domains. Pawel Waszkiewicz |
| 2005 | Constant Time Generation of Linear Extensions. Akimitsu Ono, Shin-Ichi Nakano |
| 2005 | Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals. Daniel Meister |
| 2005 | Deterministic Automata on Unranked Trees. Julien Cristau, Christof Löding, Wolfgang Thomas |
| 2005 | Exact Algorithms for Graph Homomorphisms. Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch |
| 2005 | Fully Incremental LCS Computation. Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda |
| 2005 | Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005, Proceedings Maciej Liskiewicz, Rüdiger Reischuk |
| 2005 | Generic Density and Small Span Theorem. Philippe Moser |
| 2005 | Improved Algorithms and Complexity Results for Power Domination in Graphs. Jiong Guo, Rolf Niedermeier, Daniel Raible |
| 2005 | Leftist Grammars and the Chomsky Hierarchy. Tomasz Jurdzinski, Krzysztof Lorys |
| 2005 | Logspace Optimization Problems and Their Approximability Properties. Till Tantau |
| 2005 | New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem. Andreas Brandstädt, Van Bang Le, Suhail Mahfud |
| 2005 | On Approximating Real-World Halting Problems. Sven Köhler, Christian Schindelhauer, Martin Ziegler |
| 2005 | On Finding Acyclic Subhypergraphs. Kouichi Hirata, Megumi Kuwabara, Masateru Harao |
| 2005 | On the Black-Box Complexity of Sperner's Lemma. Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven |
| 2005 | On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems. Vincenzo Bonifaci, Ugo Di Iorio, Luigi Laura |
| 2005 | On the Expressiveness of Asynchronous Cellular Automata. Benedikt Bollig |
| 2005 | On the Incompressibility of Monotone DNFs. Matthias P. Krieger |
| 2005 | On the Power of Unambiguity in Alternating Machines. Holger Spakowski, Rahul Tripathi |
| 2005 | Path Coupling Using Stopping Times. Magnus Bordewich, Martin E. Dyer, Marek Karpinski |
| 2005 | Perfect Reconstruction of Black Pixels Revisited. Hans Ulrich Simon |
| 2005 | Property Testing and the Branching Program Size of Boolean Functions. Beate Bollig |
| 2005 | Reconstructing Many Partitions Using Spectral Techniques. Joachim Giesen, Dieter Mitsche |
| 2005 | Relations Between Average-Case and Worst-Case Complexity. Aduri Pavan, N. V. Vinodchandran |
| 2005 | Shrinking Multi-pushdown Automata. Markus Holzer, Friedrich Otto |
| 2005 | Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems. Bernd Gärtner, Leo Rüst |
| 2005 | The Complexity of Querying External Memory and Streaming Data. Martin Grohe, Christoph Koch, Nicole Schweikardt |
| 2005 | The Complexity of Semilinear Problems in Succinct Representation. Peter Bürgisser, Felipe Cucker, Paulin Jacobé de Naurois |
| 2005 | The Delayed Wolfgang W. Bein, Kazuo Iwama, Lawrence L. Larmore, John Noga |
| 2005 | The Maximum Resource Bin Packing Problem. Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten Monrad Pedersen, Sanne Wøhlk |
| 2005 | The Smoothed Analysis of Algorithms. Daniel A. Spielman |
| 2005 | Translational Lemmas for Alternating TMs and PRAMs. Chuzo Iwamoto, Yoshiaki Nakashiba, Kenichi Morita, Katsunobu Imai |
| 2005 | Tree Automata and Discrete Distributed Games. Julien Bernet, David Janin |