Algorithms -- ESA 2004

This volume contains the 70 contributed papers and abstracts of two invited l- tures presented at the 12th Annual European Symposium on Algorithms (ESA 2004), held in Bergen, Norway, September 14–17, 2004. The papers in each s- tion of the proceedings are arranged alphabetically. The three distinguished - vited speakers were David Eppstein, Michael Fellows and Monika Henzinger. As in the last two years, ESA had two tracks, with separate program c- mittees, which dealt respectively with: – the design and mathematical analysis of algorithms (the “Design and A- lysis” track); – real-world applications, engineering and experimental analysis of algorithms (the “Engineering and Applications” track). Previous ESAs were held at Bad Honnef, Germany (1993); Utrecht, The Netherlands (1994); Corfu, Greece (1995); Barcelona, Spain (1996); Graz, A- tria (1997); Venice, Italy (1998); Prague, Czech Republic (1999); Saarbruc ¨ ken, ? Germany (2000); Arhus, Denmark (2001); Rome, Italy (2002); and Budapest, Hungary (2003). The predecessor to the Engineering and Applications track of ESA was the annual Workshop on Algorithm Engineering (WAE). Previous WAEs were held in Venice, Italy (1997); Saarbruc ¨ ken, Germany (1998); London, ? UK (1999); Saarbruc ¨ ken, Germany (2000); and Arhus, Denmark (2001). The proceedings of the previous ESAs were published as Springer-Verlag’s LNCS volumes 726, 855, 979, 1284, 1461, 1643, 1879, 2161, 2461, and 2832. The proceedingsoftheWAEsfrom1999onwardswerepublishedasSpringer-Verlag’s LNCS volumes 1668, 1982, and 2141.

Invited Lectures.- A Survey of FPT Algorithm Design Techniques with an Emphasis on Recent Advances and Connections to Practical Computing.- Algorithmic Aspects of Web Search Engines.- Design and Analysis Track.- Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects.- Swap and Mismatch Edit Distance.- Path Decomposition Under a New Cost Measure with Applications to Optical Network Design.- Optimal External Memory Planar Point Enclosure.- Maximizing Throughput in Multi-queue Switches.- An Improved Algorithm for CIOQ Switches.- Labeling Smart Dust.- Graph Decomposition Lemmas and Their Role in Metric Embedding Methods.- Modeling Locality: A Probabilistic Analysis of LRU and FWF.- An Algorithm for Computing DNA Walks.- Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems.- Direct Routing: Algorithms and Complexity.- Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families.- A Parameterized Algorithm for Upward Planarity Testing.- Fisher Equilibrium Price with a Class of Concave Utility Functions.- Hardness and Approximation Results for Packing Steiner Trees.- Approximation Hardness of Dominating Set Problems.- Improved Online Algorithms for Buffer Management in QoS Switches.- Time Dependent Multi Scheduling of Multicast.- Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems.- The Average Case Analysis of Partition Sorts.- A Fast Distributed Algorithm for Approximating the Maximum Matching.- Extreme Points Under Random Noise.- Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings.- On Variable-Sized Multidimensional Packing.- An Inductive Construction for Plane Laman Graphs via Vertex Splitting.- Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems.- On the Evolution of Selfish Routing.- Competitive Online Approximation of the Optimal Search Ratio.- Incremental Algorithms for Facility Location and k-Median.- Dynamic Shannon Coding.- Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries.- Negotiation-Range Mechanisms: Coalition-Resistant Markets.- Approximation Algorithms for Quickest Spanning Tree Problems.- An Approximation Algorithm for Maximum Triangle Packing.- Approximate Parameterized Matching.- Approximation of Rectangle Stabbing and Interval Stabbing Problems.- Fast 3-Coloring Triangle-Free Planar Graphs.- Approximate Unions of Lines and Minkowski Sums.- Radio Network Clustering from Scratch.- Seeking a Vertex of the Planar Matching Polytope in NC.- Equivalence of Search Capability Among Mobile Guards with Various Visibilities.- Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors.- On the Stability of Multiple Partner Stable Marriages with Ties.- Flows on Few Paths: Algorithms and Lower Bounds.- Maximum Matchings in Planar Graphs via Gaussian Elimination.- Fast Multipoint Evaluation of Bivariate Polynomials.- On Adaptive Integer Sorting.- Tiling a Polygon with Two Kinds of Rectangles.- On Dynamic Shortest Paths Problems.- Uniform Algorithms for Deterministic Construction of Efficient Dictionaries.- Fast Sparse Matrix Multiplication.- Engineering and Applications Track.- An Experimental Study of Random Knapsack Problems.- Contraction and Treewidth Lower Bounds.- Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Networks.- Comparing Real Algebraic Numbers of Small Degree.- Code Flexibility and Program Efficiency by Genericity: Improving Cgal ’s Arrangements.- Finding Dominators in Practice.- Data Migration on Parallel Disks.- Classroom Examples of Robustness Problems in Geometric Computations.- Stable Minimum Storage Merging by Symmetric Comparisons.- On Rectangular Cartograms.- Multi-word Atomic Read/Write Registers on Multiprocessor Systems.- Beyond Optimal Play in Two-Person-Zerosum Games.- Solving Geometric Covering Problems by Data Reduction.- Efficient IP Table Lookup via Adaptive Stratified Trees with Selective Reconstructions.- Super Scalar Sample Sort.- Construction of Minimum-Weight Spanners.- A Straight Skeleton Approximating the Medial Axis.- Non-additive Shortest Paths.