Algorithms – ESA 2004: 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004. Proceedings

Michael R. Fellows (auth.), Susanne Albers, Tomasz Radzik (eds.)3540230254, 9783540230250, 9783540301400

This book constitutes the refereed proceedings of the 12th Annual European Symposium on Algorithms, ESA 2004, held in Bergen, Norway, in September 2004.

The 70 revised full papers presented were carefully reviewed from 208 submissions. The scope of the papers spans the entire range of algorithmics from design and mathematical issues to real-world applications in various fields, and engineering and analysis of algorithms.

---

Table of contents :
Front Matter….Pages –
A Survey of FPT Algorithm Design Techniques with an Emphasis on Recent Advances and Connections to Practical Computing….Pages 1-2
Algorithmic Aspects of Web Search Engines….Pages 3-3
Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects….Pages 4-15
Swap and Mismatch Edit Distance….Pages 16-27
Path Decomposition Under a New Cost Measure with Applications to Optical Network Design….Pages 28-39
Optimal External Memory Planar Point Enclosure….Pages 40-52
Maximizing Throughput in Multi-queue Switches….Pages 53-64
An Improved Algorithm for CIOQ Switches….Pages 65-76
Labeling Smart Dust….Pages 77-88
Graph Decomposition Lemmas and Their Role in Metric Embedding Methods….Pages 89-97
Modeling Locality: A Probabilistic Analysis of LRU and FWF….Pages 98-109
An Algorithm for Computing DNA Walks….Pages 110-121
Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems….Pages 122-133
Direct Routing: Algorithms and Complexity….Pages 134-145
Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families….Pages 146-156
A Parameterized Algorithm for Upward Planarity Testing….Pages 157-168
Fisher Equilibrium Price with a Class of Concave Utility Functions….Pages 169-179
Hardness and Approximation Results for Packing Steiner Trees….Pages 180-191
Approximation Hardness of Dominating Set Problems….Pages 192-203
Improved Online Algorithms for Buffer Management in QoS Switches….Pages 204-215
Time Dependent Multi Scheduling of Multicast….Pages 216-227
Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems….Pages 228-239
The Average Case Analysis of Partition Sorts….Pages 240-251
A Fast Distributed Algorithm for Approximating the Maximum Matching….Pages 252-263
Extreme Points Under Random Noise….Pages 264-274
Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H -Colorings….Pages 275-286
On Variable-Sized Multidimensional Packing….Pages 287-298
An Inductive Construction for Plane Laman Graphs via Vertex Splitting….Pages 299-310
Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems….Pages 311-322
On the Evolution of Selfish Routing….Pages 323-334
Competitive Online Approximation of the Optimal Search Ratio….Pages 335-346
Incremental Algorithms for Facility Location and k -Median….Pages 347-358
Dynamic Shannon Coding….Pages 359-370
Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries….Pages 371-382
Negotiation-Range Mechanisms: Coalition-Resistant Markets….Pages 383-394
Approximation Algorithms for Quickest Spanning Tree Problems….Pages 395-402
An Approximation Algorithm for Maximum Triangle Packing….Pages 403-413
Approximate Parameterized Matching….Pages 414-425
Approximation of Rectangle Stabbing and Interval Stabbing Problems….Pages 426-435
Fast 3-Coloring Triangle-Free Planar Graphs….Pages 436-447
Approximate Unions of Lines and Minkowski Sums….Pages 448-459
Radio Network Clustering from Scratch….Pages 460-471
Seeking a Vertex of the Planar Matching Polytope in NC….Pages 472-483
Equivalence of Search Capability Among Mobile Guards with Various Visibilities….Pages 484-495
Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors….Pages 496-507
On the Stability of Multiple Partner Stable Marriages with Ties….Pages 508-519
Flows on Few Paths: Algorithms and Lower Bounds….Pages 520-531
Maximum Matchings in Planar Graphs via Gaussian Elimination….Pages 532-543
Fast Multipoint Evaluation of Bivariate Polynomials….Pages 544-555
On Adaptive Integer Sorting….Pages 556-567
Tiling a Polygon with Two Kinds of Rectangles….Pages 568-579
On Dynamic Shortest Paths Problems….Pages 580-591
Uniform Algorithms for Deterministic Construction of Efficient Dictionaries….Pages 592-603
Fast Sparse Matrix Multiplication….Pages 604-615
An Experimental Study of Random Knapsack Problems….Pages 616-627
Contraction and Treewidth Lower Bounds….Pages 628-639
Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Networks….Pages 640-651
Comparing Real Algebraic Numbers of Small Degree….Pages 652-663
Code Flexibility and Program Efficiency by Genericity: Improving Cgal ’s Arrangements….Pages 664-676
Finding Dominators in Practice….Pages 677-688
Data Migration on Parallel Disks….Pages 689-701
Classroom Examples of Robustness Problems in Geometric Computations….Pages 702-713
Stable Minimum Storage Merging by Symmetric Comparisons….Pages 714-723
On Rectangular Cartograms….Pages 724-735
Multi-word Atomic Read/Write Registers on Multiprocessor Systems….Pages 736-748
Beyond Optimal Play in Two-Person-Zerosum Games….Pages 749-759
Solving Geometric Covering Problems by Data Reduction….Pages 760-771
Efficient IP Table Lookup via Adaptive Stratified Trees with Selective Reconstructions….Pages 772-783
Super Scalar Sample Sort….Pages 784-796
Construction of Minimum-Weight Spanners….Pages 797-808
A Straight Skeleton Approximating the Medial Axis….Pages 809-821
Non-additive Shortest Paths….Pages 822-834
Back Matter….Pages –