List of accepted papers ESA'05 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 $c$-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