| 2008 | Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs. | Andrzej Lingas, Eva-Marta Lundell |
| 2008 | Randomized Rendez-Vous with Limited Memory. | Evangelos Kranakis, Danny Krizanc, Pat Morin |
| 2008 | Approximating Minimum-Power Degree and Connectivity Problems. | Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko |
| 2008 | Emergency Connectivity in Ad-Hoc Networks with Selfish Nodes. | George Karakostas, Euripides Markou |
| 2008 | Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices. | Raphal M. Jungers, Vladimir Protasov, Vincent D. Blondel |
| 2008 | An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups. | Gbor Ivanyos, Luc Sanselme, Miklos Santha |
| 2008 | Quantum Property Testing of Group Solvability. | Yoshifumi Inui, Franois Le Gall |
| 2008 | On Stateless Multihead Automata: Hierarchies and the Emptiness Problem. | Oscar H. Ibarra, Juhani Karhumki, Alexander Okhotin |
| 2008 | Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream. | Regant Y. S. Hung, Hing-Fung Ting |
| 2008 | Fixed-Parameter Algorithms for Cluster Vertex Deletion. | Falk Hffner, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier |
| 2008 | Approximating Crossing Minimization in Radial Layouts. | Seok-Hee Hong, Hiroshi Nagamochi |
| 2008 | Competitive Cost Sharing with Economies of Scale. | Martin Hoefer |
| 2008 | On Injective Colourings of Chordal Graphs. | Pavol Hell, Andr Raspaud, Juraj Stacho |
| 2008 | Bandwidth of Bipartite Permutation Graphs in Polynomial Time. | Pinar Heggernes, Dieter Kratsch, Daniel Meister |
| 2008 | Sparse Approximate Solutions to Semidefinite Programs. | Elad Hazan |
| 2008 | How to Complete a Doubling Metric. | Anupam Gupta, Kunal Talwar |
| 2008 | Minimum Cost Homomorphisms to Reflexive Digraphs. | Arvind Gupta, Pavol Hell, Mehdi Karimi, Arash Rafiey |
| 2008 | Improved Dynamic Rank-Select Entropy-Bound Structures. | Rodrigo Gonzlez, Gonzalo Navarro |
| 2008 | Approximate Polynomial gcd: Small Degree and Small Height Perturbations. | Joachim von zur Gathen, Igor E. Shparlinski |
| 2008 | Solving NP-Complete Problems with Quantum Search. | Martin Frer |
| 2008 | On the Complexity of Reconstructing H -free Graphs from Their Star Systems. | Fedor V. Fomin, Jan Kratochvl, Daniel Lokshtanov, Federico Mancini, Jan Arne Telle |
| 2008 | A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant. | Cristina G. Fernandes, Carlos Eduardo Ferreira, Christian Tjandraatmadja, Yoshiko Wakabayashi |
| 2008 | Domination in Geometric Intersection Graphs. | Thomas Erlebach, Erik Jan van Leeuwen |
| 2008 | Maximizing the Minimum Load for Selfish Agents. | Leah Epstein, Rob van Stee |
| 2008 | New Upper Bound on Vertex Folkman Numbers. | Andrzej Dudek, Vojtech Rdl |