Algorithms – ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings

Front Matter....Pages -
Designing Reliable Algorithms in Unreliable Memories....Pages 1-8
From Balanced Graph Partitioning to Balanced Metric Labeling....Pages 9-9
Fearful Symmetries: Quantum Computing, Factoring, and Graph Isomorphism....Pages 10-10
Exploring an Unknown Graph Efficiently....Pages 11-22
Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio....Pages 23-34
Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut....Pages 35-46
Relax-and-Cut for Capacitated Network Design....Pages 47-58
On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games,,....Pages 59-70
The Complexity of Games on Highly Regular Graphs....Pages 71-82
Computing Equilibrium Prices: Does Theory Meet Practice?....Pages 83-94
Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions....Pages 95-106
An Algorithm for the SAT Problem for Formulae of Linear Length....Pages 107-118
Linear-Time Enumeration of Isolated Cliques....Pages 119-130
Finding Shortest Non-separating and Non-contractible Cycles for Topologically Embedded Graphs....Pages 131-142
Delineating Boundaries for Imprecise Regions....Pages 143-154
 Exacus : Efficient and Exact Algorithms for Curves and Surfaces....Pages 155-166
Min Sum Clustering with Penalties....Pages 167-178
Improved Approximation Algorithms for Metric Max TSP....Pages 179-190
Unbalanced Graph Cuts....Pages 191-202
Low Degree Connectivity in Ad-Hoc Networks....Pages 203-214
5-Regular Graphs are 3-Colorable with Positive Probability....Pages 215-225
Optimal Integer Alphabetic Trees in Linear Time....Pages 226-237
Predecessor Queries in Constant Time?....Pages 238-248
An Algorithm for Node-Capacitated Ring Routing....Pages 249-258
On Degree Constrained Shortest Paths....Pages 259-270
A New Template for Solving p -Median Problems for Trees in Sub-quadratic Time....Pages 271-282
Roll Cutting in the Curtain Industry....Pages 283-292
Space Efficient Algorithms for the Burrows-Wheeler Backtransformation....Pages 293-304
Cache-Oblivious Comparison-Based Algorithms on Multisets....Pages 305-316
Oblivious vs. Distribution-Based Sorting: An Experimental Evaluation....Pages 317-328
Allocating Memory in a Lock-Free Manner....Pages 329-342
Generating Realistic Terrains with Higher-Order Delaunay Triangulations....Pages 343-354
I/O-Efficient Construction of Constrained Delaunay Triangulations....Pages 355-366
Convex Hull and Voronoi Diagram of Additively Weighted Points....Pages 367-378
New Tools and Simpler Algorithms for Branchwidth....Pages 379-390
Treewidth Lower Bounds with Brambles....Pages 391-402
Minimal Interval Completions....Pages 403-414
A 2-Approximation Algorithm for Sorting by Prefix Reversals....Pages 415-425
Approximating the 2-Interval Pattern Problem....Pages 426-437
A Loopless Gray Code for Minimal Signed-Binary Representations....Pages 438-447
Efficient Approximation Schemes for Geometric Problems?....Pages 448-459
Geometric Clustering to Minimize the Sum of Cluster Sizes....Pages 460-471
Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs....Pages 472-483
Packet Routing and Information Gathering in Lines, Rings and Trees....Pages 484-495
Jitter Regulation for Multiple Streams....Pages 496-507
Efficient c -Oriented Range Searching with DOP-Trees....Pages 508-519
Matching Point Sets with Respect to the Earth Mover’s Distance....Pages 520-531
Small Stretch Spanners on Dynamic Graphs....Pages 532-543
An Experimental Study of Algorithms for Fully Dynamic Transitive Closure....Pages 544-555
Experimental Study of Geometric t -Spanners....Pages 556-567
Highway Hierarchies Hasten Exact Shortest Path Queries....Pages 568-579
Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays....Pages 580-591
Fairness-Free Periodic Scheduling with Vacations....Pages 592-603
Online Bin Packing with Cardinality Constraints....Pages 604-615
Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines....Pages 616-627
Engineering Planar Separator Algorithms....Pages 628-639
 Stxxl : Standard Template Library for XXL Data Sets....Pages 640-651
Negative Cycle Detection Problem....Pages 652-663
An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees....Pages 664-676
Online View Maintenance Under a Response-Time Constraint....Pages 677-688
Online Primal-Dual Algorithms for Covering and Packing Problems....Pages 689-701
Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information....Pages 702-713
Using Fractional Primal-Dual to Schedule Split Intervals with Demands....Pages 714-725
An Approximation Algorithm for the Minimum Latency Set Cover Problem....Pages 726-733
Workload-Optimal Histograms on Streams....Pages 734-745
Finding Frequent Patterns in a String in Sublinear Time....Pages 746-757
Online Occlusion Culling....Pages 758-769
Shortest Paths in Matrix Multiplication Time....Pages 770-778
Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs....Pages 779-790
Greedy Routing in Tree-Decomposed Graphs....Pages 791-802
Making Chord Robust to Byzantine Attacks....Pages 803-814
Bucket Game with Applications to Set Multicover and Dynamic Page Migration....Pages 815-826
Bootstrapping a Hop-Optimal Network in the Weak Sensor Model....Pages 827-838
Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs....Pages 839-849
A Cutting Planes Algorithm Based Upon a Semidefinite Relaxation for the Quadratic Assignment Problem....Pages 850-861
Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and Knapsack....Pages 862-873
Robust Approximate Zeros....Pages 874-886
Optimizing a 2D Function Satisfying Unimodality Properties....Pages 887-898
Back Matter....Pages -