## Algorithms – ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, ProceedingsGerth S. Brodal, Stefano Leonardi This volume contains the 75 contributed papers and the abstracts of the three invited lectures presented at the 13th Annual European Symposium on Al- rithms (ESA 2005), held in Palma de Mallorca, Spain, October 3–6, 2005. The threedistinguishedinvitedspeakerswereGiuseppeF.Italiano,CristopherMoore and Joseph (Se?) Naor. Since 2002,ESA has consisted of two tracks, with separate programcomm- tees, which dealt respectively with – the designandmathematicalanalysis ofalgorithms(the “DesignandAna- sis” track); – real-worldapplications, engineering and experimental analysis of algorithms (the “Engineering and Applications” track). Previous ESAs in the current two track format were held in Rome, Italy (2002);Budapest,Hungary(2003);andBergen,Norway(2004).Theproceedings of these symposia were published as Springer's LNCS volumes 2461, 2832, and 3221 respectively. Papers were solicited in all areas of algorithmic research, including but not limited to algorithmic aspects of networks, approximation and on-line al- rithms, computational biology, computational geometry, computational ?nance and algorithmic game theory, data structures, database and information - trieval, external memory algorithms, graph algorithms, graph drawing, machine learning, mobile computing, pattern matching and data compression, quantum computing, and randomized algorithms. The algorithms could be sequential, distributed, or parallel. Submissions were especially encouraged in the area of mathematical programming and operations research, including combinatorial optimization, integer programming, polyhedral combinatorics, and semide?nite programming. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Designing Reliable Algorithms in Unreliable Memories | 1 |

From Balanced Graph Partitioning to Balanced Metric Labeling | 9 |

Quantum Computing Factoring and Graph Isomorphism | 10 |

Exploring an Unknown Graph Efficiently | 11 |

Online Routing in Faulty Meshes with Sublinear Comparative Time and Traffic Ratio | 23 |

Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut | 35 |

RelaxandCut for Capacitated Network Design | 47 |

On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games | 59 |

Problems? | 448 |

Geometric Clustering to Minimize the Sum of Cluster Sizes | 460 |

Approximation Schemes for Minimum 2Connected Spanning Subgraphs in Weighted Planar Graphs | 472 |

Packet Routing and Information Gathering in Lines Rings and Trees | 484 |

Jitter Regulation for Multiple Streams Extended Abstract | 496 |

Efficient cOriented Range Searching with DOPTrees | 508 |

Matching Point Sets with Respect to the Earth Movers Distance | 520 |

Small Stretch Spanners on Dynamic Graphs | 532 |

The Complexity of Games on Highly Regular Graphs | 71 |

Does Theory Meet Practice? | 83 |

Exploiting Sphere Cut Branch Decompositions | 95 |

An Algorithm for the SAT Problem for Formulae of Linear Length | 107 |

LinearTime Enumeration of Isolated Cliques | 119 |

Finding Shortest Nonseparating and Noncontractible Cycles for Topologically Embedded Graphs | 131 |

Delineating Boundaries for Imprecise Regions | 143 |

Efﬁcient and Exact Algorithms for Curves and Surfaces | 155 |

Min Sum Clustering with Penalties | 167 |

Improved Approximation Algorithms for Metric Max TSP | 179 |

Unbalanced Graph Cuts | 191 |

Low Degree Connectivity in AdHoc Networks | 203 |

5Regular Graphs are 3Colorable with Positive Probability | 215 |

Optimal Integer Alphabetic Trees in Linear Time | 226 |

Predecessor Queries in Constant Time? | 238 |

An Algorithm for NodeCapacitated Ring Routing | 249 |

On Degree Constrained Shortest Paths | 259 |

Extended Abstract | 271 |

Extended Abstract | 283 |

Space Efficient Algorithms for the BurrowsWheeler Backtransformation | 293 |

CacheOblivious ComparisonBased Algorithms on Multisets | 305 |

An Experimental Evaluation | 317 |

Allocating Memory in a LockFree Manner | 329 |

Generating Realistic Terrains with HigherOrder Delaunay Triangulations | 343 |

IOEfficient Construction of Constrained Delaunay Triangulations | 355 |

Convex Hull and Voronoi Diagram of Additively Weighted Points | 367 |

New Tools and Simpler Algorithms for Branchwidth | 379 |

Treewidth Lower Bounds with Brambles | 391 |

Minimal Interval Completions | 403 |

A 2Approximation Algorithm for Sorting by Preﬁx Reversals | 415 |

Approximating the 2Interval Pattern Problem | 426 |

A Loopless Gray Code for Minimal SignedBinary Representations | 438 |

An Experimental Study of Algorithms for Fully Dynamic Transitive Closure | 544 |

Experimental Study of Geometric tSpanners | 556 |

Highway Hierarchies Hasten Exact Shortest Path Queries | 568 |

Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays | 580 |

FairnessFree Periodic Scheduling with Vacations | 592 |

Online Bin Packing with Cardinality Constraints | 604 |

Fast Monotone 3Approximation Algorithm for Scheduling Related Machines | 616 |

Engineering Planar Separator Algorithms | 628 |

Standard Template Library for XXL Data Sets | 640 |

Negative Cycle Detection Problem | 652 |

Monotone Boolean Functions and Game Trees | 664 |

Online View Maintenance Under a ResponseTime Constraint | 677 |

Online PrimalDual Algorithms for Covering and Packing Problems | 689 |

Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information | 702 |

Using Fractional PrimalDual to Schedule Split Intervals with Demands | 714 |

An Approximation Algorithm for the Minimum Latency Set Cover Problem | 726 |

WorkloadOptimal Histograms on Streams | 734 |

Finding Frequent Patterns in a String in Sublinear Time | 746 |

Online Occlusion Culling | 758 |

Shortest Paths in Matrix Multiplication Time Extended Abstract | 770 |

Computing Common Intervals of K Permutations with Applications to Modular Decomposition of Graphs | 779 |

Greedy Routing in TreeDecomposed Graphs | 791 |

Making Chord Robust to Byzantine Attacks | 803 |

Bucket Game with Applications to Set Multicover and Dynamic Page Migration | 815 |

Bootstrapping a HopOptimal Network in the Weak Sensor Model | 827 |

Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs | 839 |

A Cutting Planes Algorithm Based Upon a Semideﬁnite Relaxation for the Quadratic Assignment Problem | 850 |

Approximation Complexity of minmax Regret Versions of Shortest Path Spanning Tree and Knapsack | 862 |

Robust Approximate Zeros Extended Abstract | 874 |

Optimizing a 2D Function Satisfying Unimodality Properties | 887 |

899 | |

### Other editions - View all

### Common terms and phrases

2-interval apply approximation algorithm block buffer cache Cartesian tree cell chordal graph cluster competitive ratio complexity Computer Science connected consider constant constraints construction contains corresponding cost cycle data structure defined Delaunay Delaunay triangulation denote disk dynamic edge elements equilibrium fractional function G.S. Brodal given graph G greedy heuristic implementation input instance integer intersection interval interval graph iteration k-clustering Lemma length Leonardi Eds linear LNCS logn lower bound machine maximum memory min-max minimal minimum Nash equilibrium node NP-hard obtain online algorithm optimal pair partition peers permutation planar graphs points polygon polynomial problem Proc programming Proof query random recursive routing running schedule scheme Section sequence shortest path solution spanner step strategy subgraph subset subtree Theorem tree treewidth triangulation update valley variables vertex vertices Voronoi diagram weight