List of accepted papers for ESA 2005: Design and Analysis Track: A 2-Approximation Algorithm for Sorting by Prefix Reversals Johannes Fischer and Simon W. Ginzinger Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs Andreas Björklund An algorithm for the SAT problem for formulae of linear length Magnus Wahlström A Loopfree Gray Code for Minimal Signed-Binary Representations Gurmeet Singh Manku and Joe Sawada Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs Sergio Cabello and Bojan Mohar Improved Approximation Algorithms for Metric Max TSP Zhi-Zhong Chen and Takayuki Nagoya A New Template for Solving p-Median Problems for Trees in Sub-quadratic Time (Extended Abstract) Robert R. Benkoczi AND Binay. K. Bhattacharya Computing common intervals of K permutations, with applications to modular decomposition of graphs Anne Bergeron, Cedric Chauve, Fabien de Montgolfier, Mathieu Raffinot Complexity of Robust Approximate Zeros Vikram Sharma and Zilin Du and Chee K. Yap Efficient Approximation Schemes for Geometric Problems? Dániel Marx Optimal Integer Alphabetic Trees in Linear Time T. C. Hu and Lawrence L. Larmore and J. David Morgenthaler Roll cutting in the curtain industry, or: A well-solvable allocation problem A Alfieri, SL van de Velde, GJ Woeginger An approximation algorithm for the minimum latency set cover problem Refael Hassin and Asaf Levin Online Bin Packing with Cardinality Constraints Leah Epstein Using Fractional Primal-Dual to Schedule Split Intervals with Demands Reuven Bar-Yehuda and Dror Rawitz Making Chord Robust to Byzantine Attacks Amos Fiat and Jared Saia and Maxwell Young On degree constrained shortest paths Samir Khuller and Kwangil Lee and Mark Shayman Online Routing in Faulty Meshes with Sub-Linear Comparative Time and Traffic Ratio Stefan Rührup and Christian Schindelhauer Small stretch spanners on dynamic graphs Giorgio Ausiello and Paolo G. Franciosa and Giuseppe F. Italiano 5-Regular Multi-Graphs are 3-Colorable with Independent of their Size Positive Probability J. Diaz and G. Grammatikopoulos and A.C. Kaporis and L.M. Kirousis and X. Perez and D.G. Sotiropoulos On the price of anarchy and stability of correlated equilibria of linear congestion games George Christodoulou and Elias Koutsoupias Packet Routing and Information Gathering in Lines, Rings and Trees Yossi Azar and Rafi Zachut Low Degree Connectivity in Ad-hoc Networks Ludek Kucera Bucket Game with Applications to Set Multicover and Dynamic Page Migration Marcin Bienkowski and Jaroslaw Byrka Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs Andre Berger, Artur Czumaj, Michelangelo Grigni, and Hairong Zhao Online View Maintenance under a Response-Time Constraint Kamesh Munagala and Jun Yang and Hai Yu The Complexity of Games on Highly Regular Graphs (Extended Abstract) Konstantinos Daskalakis and Christos H. Papadimitriou An algorithm for node-capacitated ring routing Andras Frank and Zoltan Kiraly and Balazs Kotnyek New tools and simpler algorithms for branchwidth C.Paul and J.A.Telle Efficient $-Oriented Range Searching with DOP-Trees Mark de Berg and Herman Haverkort and Micha Streppel Fast monotone 3-approximation algorithm for scheduling related machines Annamaria Kovacs Minimal interval completions Pinar Heggernes and Karol Suchan and Ioan Todinca and Yngve Villanger Linear-Time Enumeration of Isolated Cliques Hiro Ito, Kazuo Iwama, and Tsuyoshi Osumi Jitter Regulation for Multiple Streams David Hay and Gabriel Scalosub Predecessor Queries in Constant Time? Marek Karpinski and Yakov Nekrich Approximating the 2-Interval Pattern problem Maxime Crochemore and Danny Hermelin and Gad M. Landau and Stephane Vialette Shortest Paths in Matrix Multiplication Time Piotr Sankowski Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions Frederic Dorn and Eelko Penninkx and Hans L. Bodlaender and Fedor V. Fomin Min Sum Clustering with Penalties Refael Hassin and Einat Or An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees Ferdinando Cicalese and Eduardo Sany Laber Matching Point Sets with respect to the Earth Mover's Distance Sergio Cabello and Panos Giannopoulos and Christian Knauer and Günter Rote Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delay A.V.Fishkin and K.Jansen and S.Sevastianov and R.Sitters Greedy Routing in Tree-Decomposed Graphs Pierre Fraigniaud Fairness-Free Periodic Scheduling Jiri Sgall and Hadas Shachnai and Tami Tamir Exploring an unknown graph efficiently Rudolf Fleischer and Gerhard Trippen Online Primal-Dual Algorithms for Covering and Packing Problems Niv Buchbinder and Joseph (Seffi) Naor Unbalanced Graph Cuts Ara Hayrapetyan and David Kempe and Martin Pal and Zoya Svitkina Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack Hassene Aissi and Cristina Bazgan and Daniel Vanderpooten Bootstrapping a Hop-optimal Network in the Weak Sensor Model Martin Farach-Colton and Rohan Fernandes and Miguel A. Mosteiro Workload-Optimal Histograms on Streams S. Muthukrishnan and M. Strauss and X. Zheng Finding Frequent Patterns in a String in Sublinear Time Petra Berenbrink and Funda Ergun and Tom Friedetzky Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information Yigal Bejerano, Joseph (Seffi) Naor, and Alexander Sprintson Cache-oblivious comparison-based algorithms on multisets Arash Farzan and Paolo Ferragina and Gianni Franceschini and J. Ian Munro Geometric clustering to minimize the sum of cluster sizes Vittorio Bilo and Ioannis Caragiannis and Christos Kaklamanis and Panagiotis Kanellopoulos Optimizing a 2D Function Satisfying Unimodality Properties Erik D. Demaine and Stefan Langerman Engineering and Applications Track: Experimental study of geometric t-spanners Mohammad Farshi and Joachim Gudmundsson I/O-Efficient Construction of Constrained Delaunay Triangulations Pankaj K. Agarwal and Lars Arge and Ke Yi Delineating boundaries for imprecise regions Iris Reinbacher and Marc Benkert and Marc van Kreveld and Joseph S.B. Mitchell and Alexander Wolff Generating Realistic Terrains with Higher-Order Delaunay Triangulations Thierry de Kok and Marc van Kreveld and Maarten Loffler Space Efficient Algorithms for the Burrows-Wheeler Backtransformation Ulrich Lauther and Tamas Lukovszki Stxxl: Standard Template Library for XXL Data Sets Roman Dementiev and Lutz Kettner and Peter Sanders Treewidth Lower Bounds with Brambles Hans L. Bodlaender and Alexander Grigoriev and Arie M. C. A. Koster An Experimental Study of Algorithms for Fully Dynamic Transitive Closure Ioannis Krommidas and Christos Zaroliagis Allocating memory in a lock-free manner Anders Gidenstam and Marina Papatriantafilou and Philippas Tsigas Engineering Planar Separator Algorithms Martin Holzer and Grigorios Prasinos and Frank Schulz and Dorothea Wagner and Christos Zaroliagis Convex Hull and Voronoi Diagram of Additively Weighted Points Christophe Delage and Jean-Daniel Boissonnat A Cutting planes Algorithm based upon a Semidefinite relaxation for the Quadratic Assignment Problem Alain Faye and Frédéric Roupin Heuristic improvements for computing maximum multicommodity flow and minimum multicut Garima Batra and Naveen Garg and Garima Gupta Oblivious vs. Distribution-based Sorting: An Experimental Evaluation Geeta Chaudhry and Thomas H. Cormen Computing Equilibrium Prices: Does Theory Meet Practice? Bruno Codenotti and Benton McCune and Rajiv Raman and Kasturi Varadarajan Highway Hierarchies Hasten Exact Shortest Path Queries Peter Sanders and Dominik Schultes EXACUS---Efficient and Exact Algorithms for Curves and Surfaces Eric Berberich and Arno Eigenwillig and Michael Hemmer and Susan Hert and Lutz Kettner and Kurt Mehlhorn and Joachim Reichel and Online Occlusion Culling Gereon Frahling and Jens Krokowski Relax-and-cut for capacitated network design Georg Kliewer and Larissa Timajev Negative Cycle Detection Wong Chi Him and Tam Yiu Cheong