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

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 -