Algorithms – ESA 2000: 8th Annual European Symposium Saarbrücken, Germany, September 5–8, 2000 Proceedings

Monika Henzinger (auth.), Mike S. Paterson (eds.)354041004X, 9783540410041

This book constitutes the refereed proceedings of the 8th Annual European Symposium on Algorithms, ESA 2000, held in Saarbrücken, Germany in September 2000. The 39 revised full papers presented together with two invited papers were carefully reviewed and selected for inclusion in the book. Among the topics addressed are parallelism, distributed systems, approximation, combinatorial optimization, computational biology, computational geometry, external-memory algorithms, graph algorithms, network algorithms, online algorithms, data compression, symbolic computation, pattern matching, and randomized algorithms.

---

Table of contents :
Web Information Retrieval – an Algorithmic Perspective….Pages 1-8
Computational Biology — Algorithms and More….Pages 9-19
Polygon Decomposition for Efficient Construction of Minkowski Sums….Pages 20-31
An Approximation Algorithm for Hypergraph Max k -Cut with Given Sizes of Parts….Pages 32-41
Offline List Update is NP-hard….Pages 42-51
Computing Largest Common Point Sets under Approximate Congruence….Pages 52-64
Online Algorithms for Caching Multimedia Streams….Pages 64-75
On Recognizing Cayley Graphs….Pages 76-87
Fast Algorithms for Even/Odd Minimum Cuts and Generalizations….Pages 88-99
Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs….Pages 100-112
Exact Point Pattern Matching and the Number of Congruent Triangles in a Three-Dimensional Pointset….Pages 112-119
Range Searching over Tree Cross Products….Pages 120-131
A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem….Pages 132-142
The Minimum Range Assignment Problem on Linear Radio Networks….Pages 143-154
Property Testing in Computational Geometry….Pages 155-166
On R-Trees with Low Stabbing Number….Pages 167-178
K-D Trees Are Better when Cut on the Longest Side….Pages 179-190
On Multicriteria Online Problems….Pages 191-201
Online Scheduling Revisited….Pages 202-210
Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem….Pages 211-219
I/O-Efficient Well-Separated Pair Decomposition and Its Applications….Pages 221-232
Higher Order Delaunay Triangulations….Pages 232-243
On Representations of Algebraic-Geometric Codes for List Decoding….Pages 244-255
Minimizing a Convex Cost Closure Set….Pages 256-267
Preemptive Scheduling with Rejection….Pages 268-277
Simpler and Faster Vertex-Connectivity Augmentation Algorithms….Pages 278-289
Scheduling Broadcasts in Wireless Networks….Pages 290-301
Jitter Regulation in an Internet Router with Delay Consideration….Pages 302-313
Approximation of Curvature-Constrained Shortest Paths through a Sequence of Points….Pages 314-325
Resource Constrained Shortest Paths….Pages 326-337
On the Competitiveness of Linear Search….Pages 338-345
Maintaining a Minimum Spanning Tree under Transient Node Failures….Pages 346-355
Minimum Depth Graph Embedding….Pages 356-367
New Algorithms for Two-Label Point Labeling….Pages 368-380
Analysing the Cache Behaviour of Non-uniform Distribution Sorting Algorithms….Pages 380-391
How Helpers Hasten h -Relations….Pages 392-402
Computing Optimal Linear Layouts of Trees in Linear Time….Pages 403-414
Coloring Sparse Random Graphs in Polynomial Average Time….Pages 415-426
Restarts Can Help in the On-Line Minimization of the Maximum Delivery Time on a Single Machine….Pages 427-436
Collision Detection Using Bounding Boxes: Convexity Helps….Pages 437-448