| 2008 | A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant. Cristina G. Fernandes, Carlos Eduardo Ferreira, Christian Tjandraatmadja, Yoshiko Wakabayashi |
| 2008 | A Representation Theorem for Union-Difference Families and Application. Binh-Minh Bui-Xuan, Michel Habib |
| 2008 | Algorithms to Locate Errors Using Covering Arrays. Conrado Martínez, Lucia Moura, Daniel Panario, Brett Stevens |
| 2008 | An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups. Gábor Ivanyos, Luc Sanselme, Miklos Santha |
| 2008 | An Improved Algorithm Finding Nearest Neighbor Using Kd-trees. Rina Panigrahy |
| 2008 | Approximate Polynomial gcd: Small Degree and Small Height Perturbations. Joachim von zur Gathen, Igor E. Shparlinski |
| 2008 | Approximating Crossing Minimization in Radial Layouts. Seok-Hee Hong, Hiroshi Nagamochi |
| 2008 | Approximating Minimum-Power Degree and Connectivity Problems. Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko |
| 2008 | Approximating Steiner Networks with Node Weights. Zeev Nutov |
| 2008 | Approximation Algorithms for k-Hurdle Problems. Brian C. Dean, Adam Griffis, Adam Whitley |
| 2008 | Average Rate Speed Scaling. Nikhil Bansal, David P. Bunde, Ho-Leung Chan, Kirk Pruhs |
| 2008 | Bandwidth of Bipartite Permutation Graphs in Polynomial Time. Pinar Heggernes, Dieter Kratsch, Daniel Meister |
| 2008 | Collective Additive Tree Spanners of Homogeneously Orderable Graphs. Feodor F. Dragan, Chenyu Yan, Yang Xiang |
| 2008 | Coloring Geometric Range Spaces. Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, Shakhar Smorodinsky |
| 2008 | Comparing and Aggregating Partially Resolved Trees. Mukul S. Bansal, Jianrong Dong, David Fernández-Baca |
| 2008 | Competitive Cost Sharing with Economies of Scale. Martin Hoefer |
| 2008 | Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices. Raphaël M. Jungers, Vladimir Protasov, Vincent D. Blondel |
| 2008 | Domination in Geometric Intersection Graphs. Thomas Erlebach, Erik Jan van Leeuwen |
| 2008 | Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs. Andrzej Lingas, Eva-Marta Lundell |
| 2008 | Emergency Connectivity in Ad-Hoc Networks with Selfish Nodes. George Karakostas, Euripides Markou |
| 2008 | Energy Efficient Monitoring in Sensor Networks. Amol Deshpande, Samir Khuller, Azarakhsh Malekian, Mohammed Toossi |
| 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 Hüffner, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier |
| 2008 | Fully-Compressed Suffix Trees. Luís M. S. Russo, Gonzalo Navarro, Arlindo L. Oliveira |
| 2008 | Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers. Marcin Bienkowski, Aleksander Madry |
| 2008 | Guided Search and a Faster Deterministic Algorithm for 3-SAT. Dominik Scheder |
| 2008 | How to Complete a Doubling Metric. Anupam Gupta, Kunal Talwar |
| 2008 | I/O-Efficient Point Location in a Set of Rectangles. Yakov Nekrich |
| 2008 | Improved Dynamic Rank-Select Entropy-Bound Structures. Rodrigo González, Gonzalo Navarro |
| 2008 | LATIN 2008: Theoretical Informatics, 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008, Proceedings Eduardo Sany Laber, Claudson F. Bornstein, Loana Tito Nogueira, Luérbio Faria |
| 2008 | List Update with Locality of Reference. Spyros Angelopoulos, Reza Dorrigiv, Alejandro López-Ortiz |
| 2008 | Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes. Jurek Czyzowicz, Stefan Dobrev, Thomas Fevens, Hernán González-Aguilar, Evangelos Kranakis, Jaroslav Opatrny, Jorge Urrutia |
| 2008 | Maximizing the Minimum Load for Selfish Agents. Leah Epstein, Rob van Stee |
| 2008 | Minimum Cost Homomorphisms to Reflexive Digraphs. Arvind Gupta, Pavol Hell, Mehdi Karimi, Arash Rafiey |
| 2008 | Myhill-Nerode Theorem for Recognizable Tree Series Revisited. Andreas Maletti |
| 2008 | New Upper Bound on Vertex Folkman Numbers. Andrzej Dudek, Vojtech Rödl |
| 2008 | On 2-Subcolourings of Chordal Graphs. Juraj Stacho |
| 2008 | On Dissemination Thresholds in Regular and Irregular Graph Classes. Ivan Rapaport, Karol Suchan, Ioan Todinca, Jacques Verstraëte |
| 2008 | On Injective Colourings of Chordal Graphs. Pavol Hell, André Raspaud, Juraj Stacho |
| 2008 | On Stateless Multihead Automata: Hierarchies and the Emptiness Problem. Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin |
| 2008 | On the Complexity of Reconstructing H -free Graphs from Their Star Systems. Fedor V. Fomin, Jan Kratochvíl, Daniel Lokshtanov, Federico Mancini, Jan Arne Telle |
| 2008 | On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints. Gérard Cornuéjols, François Margot |
| 2008 | Optimal Higher Order Delaunay Triangulations of Polygons. Rodrigo I. Silveira, Marc J. van Kreveld |
| 2008 | Optimization and Recognition for K 5-minor Free Graphs in Linear Time. Bruce A. Reed, Zhentao Li |
| 2008 | Origami Embedding of Piecewise-Linear Two-Manifolds. Marshall W. Bern, Barry Hayes |
| 2008 | Parallel Repetition of the Odd Cycle Game. Kooshiar Azimian, Mario Szegedy |
| 2008 | Paths and Trails in Edge-Colored Graphs. Abdelfattah Abouelaoualim, Kinkar Chandra Das, Luérbio Faria, Yannis Manoussakis, Carlos A. J. Martinhon, Rachid Saad |
| 2008 | Paths with no Small Angles. Imre Bárány, Attila Pór, Pavel Valtr |
| 2008 | Profile of Tries. GaHyun Park, Hsien-Kuei Hwang, Pierre Nicodème, Wojciech Szpankowski |
| 2008 | Pseudorandom Graphs from Elliptic Curves. Igor E. Shparlinski |
| 2008 | Ptolemaic Graphs and Interval Graphs Are Leaf Powers. Andreas Brandstädt, Christian Hundt |
| 2008 | Quantum Property Testing of Group Solvability. Yoshifumi Inui, François Le Gall |
| 2008 | Random 2-XORSAT at the Satisfiability Threshold. Hervé Daudé, Vlady Ravelomanana |
| 2008 | Randomized Rendez-Vous with Limited Memory. Evangelos Kranakis, Danny Krizanc, Pat Morin |
| 2008 | Simpler Constant-Seed Condensers. Domingos Dellamonica Jr. |
| 2008 | Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance. Sergey Bereg, Minghui Jiang, Wencheng Wang, Boting Yang, Binhai Zhu |
| 2008 | Solving NP-Complete Problems with Quantum Search. Martin Fürer |
| 2008 | Sorting and Selection with Random Costs. Stanislav Angelov, Keshav Kunal, Andrew McGregor |
| 2008 | Spanners of Complete k -Partite Geometric Graphs. Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel H. M. Smid |
| 2008 | Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms. Paul S. Bonsma, Florian Zickfeld |
| 2008 | Sparse Approximate Solutions to Semidefinite Programs. Elad Hazan |
| 2008 | Speeding-Up Lattice Reduction with Random Projections (Extended Abstract). Ali Akhavi, Damien Stehlé |
| 2008 | Stateless Near Optimal Flow Control with Poly-logarithmic Convergence. Baruch Awerbuch, Rohit Khandekar |
| 2008 | The Generalized Median Stable Matchings: Finding Them Is Not That Easy. Christine T. Cheng |
| 2008 | The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences. Richard Matthew McCutchen |
| 2008 | The Online Transportation Problem: On the Exponential Boost of One Extra Server. Christine Chung, Kirk Pruhs, Patchrawat Uthaisombut |
| 2008 | The View Selection Problem for Regular Path Queries. Sergey A. Afonin |
| 2008 | Weighted Rectilinear Approximation of Points in the Plane. Mario Alberto López, Yan Mayster |