13. ESA 2005: Palma de Mallorca, Spain

• Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano:
  Designing Reliable Algorithms in Unreliable Memories. 1-8
  
• Joseph Naor:
  From Balanced Graph Partitioning to Balanced Metric Labeling. 9
  
• Cristopher Moore:
  Fearful Symmetries: Quantum Computing, Factoring, and Graph Isomorphism. 10
  
• Rudolf Fleischer, Gerhard Trippen:
  Exploring an Unknown Graph Efficiently. 11-22
  
• Stefan Rührup, Christian Schindelhauer:
  Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio. 23-34
  
• Garima Batra, Naveen Garg, Garima Gupta:
  Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. 35-46
  
• Georg Kliewer, Larissa Timajev:
  Relax-and-Cut for Capacitated Network Design. 47-58
  
• George Christodoulou, Elias Koutsoupias:
  On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games. 59-70
  
• Konstantinos Daskalakis, Christos H. Papadimitriou:
  The Complexity of Games on Highly Regular Graphs. 71-82
  
• Bruno Codenotti, Benton McCune, Rajiv Raman, Kasturi R. Varadarajan:
  Computing Equilibrium Prices: Does Theory Meet Practice?. 83-94
  
• Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, Fedor V. Fomin:
  Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions. 95-106
  
• Magnus Wahlström:
  An Algorithm for the SAT Problem for Formulae of Linear Length. 107-118
  
• Hiro Ito, Kazuo Iwama, Tsuyoshi Osumi:
  Linear-Time Enumeration of Isolated Cliques. 119-130
  
• Sergio Cabello, Bojan Mohar:
  Finding Shortest Non-separating and Non-contractible Cycles for Topologically Embedded Graphs. 131-142
  
• Iris Reinbacher, Marc Benkert, Marc J. van Kreveld, Joseph S. B. Mitchell, Alexander Wolff:
  Delineating Boundaries for Imprecise Regions. 143-154
  
• Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Lutz Kettner, Kurt Mehlhorn, Joachim Reichel, Susanne Schmitt, Elmar Schömer, Nicola Wolpert:
  EXACUS: Efficient and Exact Algorithms for Curves and Surfaces. 155-166
  
• Refael Hassin, Einat Or:
  Min Sum Clustering with Penalties. 167-178
  
• Zhi-Zhong Chen, Takayuki Nagoya:
  Improved Approximation Algorithms for Metric Max TSP. 179-190
  
• Ara Hayrapetyan, David Kempe, Martin Pál, Zoya Svitkina:
  Unbalanced Graph Cuts. 191-202
  
• Ludek Kucera:
  Low Degree Connectivity in Ad-Hoc Networks. 203-214
  
• Josep Díaz, G. Grammatikopoulos, Alexis C. Kaporis, Lefteris M. Kirousis, Xavier Pérez, Dionisios G. Sotiropoulos:
  5-Regular Graphs are 3-Colorable with Positive Probability. 215-225
  
• T. C. Hu, Lawrence L. Larmore, J. David Morgenthaler:
  Optimal Integer Alphabetic Trees in Linear Time. 226-237
  
• Marek Karpinski, Yakov Nekrich:
  Predecessor Queries in Constant Time?. 238-248
  
• András Frank, Zoltán Király, Balázs Kotnyek:
  An Algorithm for Node-Capacitated Ring Routing. 249-258
  
• Samir Khuller, Kwangil Lee, Mark A. Shayman:
  On Degree Constrained Shortest Paths. 259-270
  
• Robert Benkoczi, Binay K. Bhattacharya:
  A New Template for Solving p-Median Problems for Trees in Sub-quadratic Time. 271-282
  
• Arianna Alfieri, Steef L. van de Velde, Gerhard J. Woeginger:
  Roll Cutting in the Curtain Industry. 283-292
  
• Ulrich Lauther, Tamás Lukovszki:
  Space Efficient Algorithms for the Burrows-Wheeler Backtransformation. 293-304
  
• Arash Farzan, Paolo Ferragina, Gianni Franceschini, J. Ian Munro:
  Cache-Oblivious Comparison-Based Algorithms on Multisets. 305-316
  
• Geeta Chaudhry, Thomas H. Cormen:
  Oblivious vs. Distribution-Based Sorting: An Experimental Evaluation. 317-328
  
• Anders Gidenstam, Marina Papatriantafilou, Philippas Tsigas:
  Allocating Memory in a Lock-Free Manner. 329-342
  
• Thierry de Kok, Marc J. van Kreveld, Maarten Löffler:
  Generating Realistic Terrains with Higher-Order Delaunay Triangulations. 343-354
  
• Pankaj K. Agarwal, Lars Arge, Ke Yi:
  I/O-Efficient Construction of Constrained Delaunay Triangulations. 355-366
  
• Jean-Daniel Boissonnat, Christophe Delage:
  Convex Hull and Voronoi Diagram of Additively Weighted Points. 367-378
  
• Christophe Paul, Jan Arne Telle:
  New Tools and Simpler Algorithms for Branchwidth. 379-390
  
• Hans L. Bodlaender, Alexander Grigoriev, Arie M. C. A. Koster:
  Treewidth Lower Bounds with Brambles. 391-402
  
• Pinar Heggernes, Karol Suchan, Ioan Todinca, Yngve Villanger:
  Minimal Interval Completions. 403-414
  
• Johannes Fischer, Simon W. Ginzinger:
  A 2-Approximation Algorithm for Sorting by Prefix Reversals. 415-425
  
• Maxime Crochemore, Danny Hermelin, Gad M. Landau, Stéphane Vialette:
  Approximating the 2-Interval Pattern Problem. 426-437
  
• Gurmeet Singh Manku, Joe Sawada:
  A Loopless Gray Code for Minimal Signed-Binary Representations. 438-447
  
• Dániel Marx:
  Efficient Approximation Schemes for Geometric Problems?. 448-459
  
• Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos:
  Geometric Clustering to Minimize the Sum of Cluster Sizes. 460-471
  
• André Berger, Artur Czumaj, Michelangelo Grigni, Hairong Zhao:
  Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs. 472-483
  
• Yossi Azar, Rafi Zachut:
  Packet Routing and Information Gathering in Lines, Rings and Trees. 484-495
  
• David Hay, Gabriel Scalosub:
  Jitter Regulation for Multiple Streams. 496-507
  
• Mark de Berg, Herman J. Haverkort, Micha Streppel:
  Efficient c-Oriented Range Searching with DOP-Trees. 508-519
  
• Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote:
  Matching Point Sets with Respect to the Earth Mover's Distance. 520-531
  
• Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe F. Italiano:
  Small Stretch Spanners on Dynamic Graphs. 532-543
  
• Ioannis Krommidas, Christos D. Zaroliagis:
  An Experimental Study of Algorithms for Fully Dynamic Transitive Closure. 544-555
  
• Mohammad Farshi, Joachim Gudmundsson:
  Experimental Study of Geometric t-Spanners. 556-567
  
• Peter Sanders, Dominik Schultes:
  Highway Hierarchies Hasten Exact Shortest Path Queries. 568-579
  
• Aleksei V. Fishkin, Klaus Jansen, Sergey V. Sevastianov, René Sitters:
  Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays. 580-591
  
• Jiri Sgall, Hadas Shachnai, Tami Tamir:
  Fairness-Free Periodic Scheduling with Vacations. 592-603
  
• Leah Epstein:
  Online Bin Packing with Cardinality Constraints. 604-615
  
• Annamária Kovács:
  Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines. 616-627
  
• Martin Holzer, Grigorios Prasinos, Frank Schulz, Dorothea Wagner, Christos D. Zaroliagis:
  Engineering Planar Separator Algorithms. 628-639
  
• Roman Dementiev, Lutz Kettner, Peter Sanders:
  : Standard Template Library for XXL Data Sets. 640-651
  
• Chi-Him Wong, Yiu-Cheong Tam:
  Negative Cycle Detection Problem. 652-663
  
• Ferdinando Cicalese, Eduardo Sany Laber:
  An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees. 664-676
  
• Kamesh Munagala, Jun Yang, Hai Yu:
  Online View Maintenance Under a Response-Time Constraint. 677-688
  
• Niv Buchbinder, Joseph Naor:
  Online Primal-Dual Algorithms for Covering and Packing Problems. 689-701
  
• Yigal Bejerano, Joseph Naor, Alexander Sprintson:
  Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information. 702-713
  
• Reuven Bar-Yehuda, Dror Rawitz:
  Using Fractional Primal-Dual to Schedule Split Intervals with Demands. 714-725
  
• Refael Hassin, Asaf Levin:
  An Approximation Algorithm for the Minimum Latency Set Cover Problem. 726-733
  
• S. Muthukrishnan, Martin Strauss, X. Zheng:
  Workload-Optimal Histograms on Streams. 734-745
  
• Petra Berenbrink, Funda Ergün, Tom Friedetzky:
  Finding Frequent Patterns in a String in Sublinear Time. 746-757
  
• Gereon Frahling, Jens Krokowski:
  Online Occlusion Culling. 758-769
  
• Piotr Sankowski:
  Shortest Paths in Matrix Multiplication Time. 770-778
  
• Anne Bergeron, Cedric Chauve, Fabien de Montgolfier, Mathieu Raffinot:
  Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs. 779-790
  
• Pierre Fraigniaud:
  Greedy Routing in Tree-Decomposed Graphs. 791-802
  
• Amos Fiat, Jared Saia, Maxwell Young:
  Making Chord Robust to Byzantine Attacks. 803-814
  
• Marcin Bienkowski, Jaroslaw Byrka:
  Bucket Game with Applications to Set Multicover and Dynamic Page Migration. 815-826
  
• Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro:
  Bootstrapping a Hop-Optimal Network in the Weak Sensor Model. 827-838
  
• Andreas Björklund:
  Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs. 839-849
  
• Alain Faye, Frédéric Roupin:
  A Cutting Planes Algorithm Based Upon a Semidefinite Relaxation for the Quadratic Assignment Problem. 850-861
  
• Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten:
  Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and Knapsack. 862-873
  
• Vikram Sharma, Zilin Du, Chee-Keng Yap:
  Robust Approximate Zeros. 874-886
  
• Erik D. Demaine, Stefan Langerman:
  Optimizing a 2D Function Satisfying Unimodality Properties. 887-898