Algorithms — ESA 2001: 9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings

External Memory Data Structures....Pages 1-29
Some Algorithmic Problems in Large Networks....Pages 30-32
Exact and Approximate Distances in Graphs — A Survey....Pages 33-48
Strongly Competitive Algorithms for Caching with Pipelined Prefetching....Pages 49-61
Duality between Prefetching and Queued Writing with Parallel Disks....Pages 62-73
Online Bin Coloring....Pages 74-85
A General Decomposition Theorem for the k -Server Problem....Pages 86-97
Buying a Constant Competitive Ratio for Paging....Pages 98-108
Simple Minimal Perfect Hashing in Less Space....Pages 109-120
Cuckoo Hashing....Pages 121-133
Coupling Variable Fixing Algorithms for the Automatic Recording Problem....Pages 134-145
Approximation Algorithms for Scheduling Malleable Tasks under Precedence Constraints....Pages 146-157
On the Approximability of the Minimum Test Collection Problem....Pages 158-169
Finding Approximate Repetitions under Hamming Distance....Pages 170-181
SNPs Problems, Complexity, and Algorithms....Pages 182-193
A FPTAS for Approximating the Unrelated Parallel Machines Scheduling Problem with Costs....Pages 194-205
Grouping Techniques for Scheduling Problems: Simpler and Faster....Pages 206-217
A 2-Approximation Algorithm for the Multi-vehicle Scheduling Problem on a Path with Release and Handling Times....Pages 218-229
A Simple Shortest Path Algorithm with Linear Average Time....Pages 230-241
A Heuristic for Dijkstra’s Algorithm with Many Targets and Its Use in Weighted Matching Algorithms....Pages 242-253
A Separation Bound for Real Algebraic Expressions....Pages 254-265
Property Testing with Geometric Queries....Pages 266-277
Smallest Color-Spanning Objects....Pages 278-289
Explicit Deterministic Constructions for Membership in the Bitprobe Model....Pages 290-299
Lossy Dictionaries....Pages 300-311
Splitting a Delaunay Triangulation in Linear Time....Pages 312-320
A Fast Algorithm for Approximating the Detour of a Polygonal Chain....Pages 321-332
An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee....Pages 333-344
Distributed O ( Δ log n )-Edge-Coloring Algorithm....Pages 345-355
Modeling Replica Placement in a Distributed File System: Narrowing the Gap between Analysis and Simulation....Pages 356-367
Computing Cycle Covers without Short Cycles....Pages 368-379
A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth....Pages 380-390
Lower Bounds and Exact Algorithms for the Graph Partitioning Problem Using Multicommodity Flows....Pages 391-403
Fast Pricing of European Asian Options with Provable Accuracy: Single-Stock and Basket Options....Pages 404-415
Competitive Auctions for Multiple Digital Goods....Pages 416-427
Algorithms for Efficient Filtering in Content-Based Multicast....Pages 428-439
Approximation Algorithms for Minimum-Time Broadcast under the Vertex-Disjoint Paths Mode....Pages 440-451
Round Robin Is Optimal for Fault-Tolerant Broadcasting on Wireless Networks....Pages 452-463
Online and Offline Distance Constrained Labeling of Disk Graphs....Pages 464-475
Approximate Distance Labeling Schemes....Pages 476-487
On the Parameterized Complexity of Layered Graph Drawing....Pages 488-499
A General Model of Undirected Web Graphs....Pages 500-511
Packing Cycles and Cuts in Undirected Graphs....Pages 512-523
Greedy Algorithms for Minimisation Problems in Random Regular Graphs....Pages 524-536