| 2005 | Online Interval Coloring and Variants. | Leah Epstein, Meital Levy |
| 2005 | Reordering Buffer Management for Non-uniform Cost Models. | Matthias Englert, Matthias Westermann |
| 2005 | Fast Neighbor Joining. | Isaac Elias, Jens Lagergren |
| 2005 | Approximation Algorithms for Euclidean Group TSP. | Khaled M. Elbassioni, Aleksei V. Fishkin, Nabil H. Mustafa, Ren Sitters |
| 2005 | New Approaches for Virtual Private Network Design. | Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo, Martin Skutella |
| 2005 | On the Existence of Hamiltonian Cycles in Random Intersection Graphs. | Charilaos Efthymiou, Paul G. Spirakis |
| 2005 | Weighted Automata and Weighted Logics. | Manfred Droste, Paul Gastin |
| 2005 | Stability and Similarity of Link Analysis Ranking Algorithms. | Debora Donato, Stefano Leonardi, Panayiotis Tsaparas |
| 2005 | Optimal Cover Time for a Graph-Based Coupon Collector Process. | Nedialko B. Dimitrov, C. Greg Plaxton |
| 2005 | Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins. | Martin Dietzfelbinger, Christoph Weidling |
| 2005 | Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. | Scott Diehl, Dieter van Melkebeek |
| 2005 | Compositional Verification of Asynchronous Processes via Constraint Solving. | Giorgio Delzanno, Maurizio Gabbrielli |
| 2005 | Probabilistic Polynomial-Time Semantics for a Protocol Security Logic. | Anupam Datta, Ante Derek, John C. Mitchell, Vitaly Shmatikov, Mathieu Turuani |
| 2005 | A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata. | Eugen Czeizler, Jarkko Kari |
| 2005 | Concurrent Zero Knowledge in the Public-Key Model. | Giovanni Di Crescenzo, Ivan Visconti |
| 2005 | Asynchronous Perfectly Secure Communication over One-Time Pads. | Giovanni Di Crescenzo, Aggelos Kiayias |
| 2005 | Spatial Logics for Bigraphs. | Giovanni Conforti, Damiano Macedonio, Vladimiro Sassone |
| 2005 | Label-Guided Graph Exploration by a Finite Automaton. | Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, David Peleg |
| 2005 | On the Wake-Up Problem in Radio Networks. | Bogdan S. Chlebus, Leszek Gasieniec, Dariusz R. Kowalski, Tomasz Radzik |
| 2005 | Worst Case Optimal Union-Intersection Expression Evaluation. | Ehsan Chiniforooshan, Arash Farzan, Mehdi Mirzazadeh |
| 2005 | Combining Intruder Theories. | Yannick Chevalier, Michal Rusinowitch |
| 2005 | Lower Bounds for Circuits with Few Modular and Symmetric Gates. | Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen |
| 2005 | The Complexity of Stochastic Rabin and Streett Games'. | Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger |
| 2005 | Dynamic Bin Packing of Unit Fractions Items. | Wun-Tat Chan, Tak Wah Lam, Prudence W. H. Wong |
| 2005 | Hybrid Trapdoor Commitments and Their Applications. | Dario Catalano, Ivan Visconti |