Lars Arge (auth.), Friedhelm Meyer auf der Heide (eds.)3540424938, 9783540424932
The 41 revised full papers presented together with three invited contributions were carefully reviewed and selected from 102 submissions. The papers are organized in topical sections on caching and prefetching, online algorithms, data structures, optimization and approximation, sequences, scheduling, shortest paths, geometry, distributed algorithms, graph algorithms, pricing, broadcasting and multicasting, graph labeling and graph drawing, and graphs.
Table of contents :
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
Reviews
There are no reviews yet.