| 2008 | 3-Message NP Arguments in the BPK Model with Optimal Soundness and Zero-Knowledge. Giovanni Di Crescenzo, Helger Lipmaa |
| 2008 | A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths. Jonathan Backer, David G. Kirkpatrick |
| 2008 | A Game Theoretic Approach for Efficient Graph Coloring. Panagiota N. Panagopoulou, Paul G. Spirakis |
| 2008 | A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs. Hans L. Bodlaender, Eelko Penninkx, Richard B. Tan |
| 2008 | A Method to Overcome Computer Word Size Limitation in Bit-Parallel Pattern Matching. M. Oguzhan Külekci |
| 2008 | A New Algorithm for Finding Trees with Many Leaves. Joachim Kneis, Alexander Langer, Peter Rossmanith |
| 2008 | Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga |
| 2008 | An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem. Maxim A. Babenko |
| 2008 | An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts. Mingyu Xiao |
| 2008 | Approximate Nearest Neighbor Search under Translation Invariant Hausdorff Distance. Christian Knauer, Marc Scherfenberg |
| 2008 | Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects. Karl Bringmann, Tobias Friedrich |
| 2008 | Average Update Times for Fully-Dynamic All-Pairs Shortest Paths. Tobias Friedrich, Nils Hebbinghaus |
| 2008 | Bandwidth of Bipartite Permutation Graphs. Ryuhei Uehara |
| 2008 | Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks. Daniel Delling, Giacomo Nannicini |
| 2008 | Comparing First-Fit and Next-Fit for Online Edge Coloring. Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, Rodica Mihai |
| 2008 | Computing Best Swaps in Optimal Tree Spanners. Shantanu Das, Beat Gfeller, Peter Widmayer |
| 2008 | Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. Jun Luo, Christian Wulff-Nilsen |
| 2008 | Computing Frequency Dominators and Related Problems. Loukas Georgiadis |
| 2008 | Computing the Maximum Detour of a Plane Graph in Subquadratic Time. Christian Wulff-Nilsen |
| 2008 | Computing with Priced Information: When the Value Makes the Price. Ferdinando Cicalese, Martin Milanic |
| 2008 | Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?. Tetsuo Asano |
| 2008 | Constructing the Simplest Possible Phylogenetic Network from Triplets. Leo van Iersel, Steven Kelk |
| 2008 | Covering a Point Set by Two Disjoint Rectangles. Hee-Kap Ahn, Sang Won Bae |
| 2008 | Covering a Simple Polygon by Monotone Directions. Hee-Kap Ahn, Peter Brass, Christian Knauer, Hyeon-Suk Na, Chan-Su Shin |
| 2008 | Data Stream Algorithms via Expander Graphs. Sumit Ganguly |
| 2008 | Deductive Inference for the Interiors and Exteriors of Horn Theories. Kazuhisa Makino, Hirotaka Ono |
| 2008 | Detecting Commuting Patterns by Clustering Subtrajectories. Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, Jun Luo |
| 2008 | Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD. Ali Civril, Malik Magdon-Ismail |
| 2008 | Efficient Output-Sensitive Construction of Reeb Graphs. Harish Doraiswamy, Vijay Natarajan |
| 2008 | Enumeration of Perfect Sequences of Chordal Graph. Yasuko Matsui, Ryuhei Uehara, Takeaki Uno |
| 2008 | Evaluation of General Set Expressions. Ehsan Chiniforooshan, Arash Farzan, Mehdi Mirzazadeh |
| 2008 | Faster Parameterized Algorithms for Minimum Fill-In. Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger |
| 2008 | Finding Long Paths, Cycles and Circuits. Harold N. Gabow, Shuxin Nie |
| 2008 | Firefighting on Trees: (1-1/e)-Approximation, Fixed Parameter Tractability and a Subexponential Algorithm. Leizhen Cai, Elad Verbin, Lin Yang |
| 2008 | Free-Form Surface Partition in 3-D. Danny Z. Chen, Ewa Misiolek |
| 2008 | From Tree-Width to Clique-Width: Excluding a Unit Interval Graph. Vadim V. Lozin |
| 2008 | Graph Layout Problems Parameterized by Vertex Cover. Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, Saket Saurabh |
| 2008 | Greedy Construction of 2-Approximation Minimum Manhattan Network. Zeyu Guo, He Sun, Hong Zhu |
| 2008 | How to Guard a Graph?. Fedor V. Fomin, Petr A. Golovach, Alexander Hall, Matús Mihalák, Elias Vicari, Peter Widmayer |
| 2008 | Improving the Competitive Ratio of the Online OVSF Code Assignment Problem. Shuichi Miyazaki, Kazuya Okamoto |
| 2008 | Independent Sets of Maximum Weight in Apple-Free Graphs. Andreas Brandstädt, Tilo Klembt, Vadim V. Lozin, Raffaele Mosca |
| 2008 | Inducing Polygons of Line Arrangements. Ludmila Scharf, Marc Scherfenberg |
| 2008 | König Deletion Sets and Vertex Covers above the Matching Size. Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar |
| 2008 | Leaf Powers and Their Properties: Using the Trees. Michael R. Fellows, Daniel Meister, Frances A. Rosamond, R. Sritharan, Jan Arne Telle |
| 2008 | Minimizing Total Flow-Time: The Unrelated Case. Naveen Garg, Amit Kumar, V. N. Muralidhara |
| 2008 | Minkowski Sum Selection and Finding. Cheng-Wei Luo, Hsiao-Fei Liu, Peng-An Chen, Kun-Mao Chao |
| 2008 | Multiobjective Disk Cover Admits a PTAS. Christian Glaßer, Christian Reitwießner, Heinz Schmitz |
| 2008 | Navigating in a Graph by Aid of Its Spanning Tree. Feodor F. Dragan, Martín Matamala |
| 2008 | Negation-Limited Inverters of Linear Size. Hiroki Morizumi, Genki Suzuki |
| 2008 | New Results on Optimizing Rooted Triplets Consistency. Jaroslaw Byrka, Sylvain Guillemot, Jesper Jansson |
| 2008 | New Results on the Most Significant Bit of Integer Multiplication. Beate Bollig, Jochen Klump |
| 2008 | On Labeled Traveling Salesman Problems. Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, Orestis Telelis |
| 2008 | On a Non-cooperative Model for Wavelength Assignment in Multifiber Optical Networks. Evangelos Bampas, Aris Pagourtzis, George Pierrakos, Katerina Potika |
| 2008 | On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures. Michael Lampis, Georgia Kaouri, Valia Mitsou |
| 2008 | On the Complexity of Reconfiguration Problems. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno |
| 2008 | On the Stability of Web Crawling and Web Search. Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcroft, Vahab S. Mirrokni, Shang-Hua Teng |
| 2008 | On the Stretch Factor of Convex Delaunay Graphs. Prosenjit Bose, Paz Carmi, Sébastien Collette, Michiel H. M. Smid |
| 2008 | Optimal Key Tree Structure for Deleting Two or More Leaves. Weiwei Wu, Minming Li, Enhong Chen |
| 2008 | Partitioning a Weighted Tree to Subtrees of Almost Uniform Size. Takehiro Ito, Takeaki Uno, Xiao Zhou, Takao Nishizeki |
| 2008 | Power Domination in O Daniel Raible, Henning Fernau |
| 2008 | Preprocessing Imprecise Points and Splitting Triangulations. Marc J. van Kreveld, Maarten Löffler, Joseph S. B. Mitchell |
| 2008 | Quantum Query Complexity of Boolean Functions with Small On-Sets. Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita |
| 2008 | Reachability Problems on Directed Graphs. Robert Endre Tarjan |
| 2008 | Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves. Greg Aloupis, Sébastien Collette, Erik D. Demaine, Stefan Langerman, Vera Sacristán Adinolfi, Stefanie Wuhrer |
| 2008 | Selecting Sums in Arrays. Gerth Stølting Brodal, Allan Grønlund Jørgensen |
| 2008 | Signature Theory in Holographic Algorithms. Jin-Yi Cai, Pinyan Lu |
| 2008 | Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times. Binay K. Bhattacharya, Paz Carmi, Yuzhuang Hu, Qiaosheng Shi |
| 2008 | Some Constrained Notions of Planarity. Peter Eades |
| 2008 | Sorting with Complete Networks of Stacks. Felix G. König, Marco E. Lübbecke |
| 2008 | Space-Efficient Informational Redundancy. Christian Glaßer |
| 2008 | Space-Time Tradeoffs for Longest-Common-Prefix Array Computation. Simon J. Puglisi, Andrew Turpin |
| 2008 | Squaring the Circle with Weak Mobile Robots. Yoann Dieudonné, Franck Petit |
| 2008 | Succinct and I/O Efficient Data Structures for Traversal in Trees. Craig Dillabaugh, Meng He, Anil Maheshwari |
| 2008 | Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States. Rusins Freivalds |
| 2008 | The Balanced Edge Cover Problem. Yuta Harada, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita |
| 2008 | The Complexity of Minimum Convex Coloring. Frank Kammer, Torsten Tholey |
| 2008 | The Complexity of Rationalizing Matchings. Shankar Kalyanaraman, Christopher Umans |
| 2008 | The Complexity of SPP Formula Minimization. David Buchfuhrer |
| 2008 | The Isolation Game: A Game of Distances. Yingchao Zhao, Wei Chen, Shang-Hua Teng |
| 2008 | Tree Decontamination with Temporary Immunity. Paola Flocchini, Bernard Mans, Nicola Santoro |
| 2008 | Unbounded-Error Quantum Query Complexity. Ashley Montanaro, Harumichi Nishimura, Rudy Raymond |
| 2008 | Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol. Eric Goles Ch., Cedric Little, Ivan Rapaport |