Algorithms - ESA 2000: 8th Annual European Symposium Saarbrücken, Germany, September 5-8, 2000 ProceedingsMichael S. Paterson 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. |
Contents
Web Information Retrieval An Algorithmic Perspective | 1 |
Computational Biology Algorithms and More | 9 |
Polygon Decomposition for Efficient Construction of Minkowski Sums | 20 |
An Approximation Algorithm for Hypergraph Max kCut with Given Sizes of Parts | 32 |
Offline List Update Is NPHard | 42 |
Computing Largest Common Point Sets under Approximate Congruence | 52 |
Online Algorithms for Caching Multimedia Streams | 64 |
On Recognizing Cayley Graphs | 76 |
Higher Order Delaunay Triangulations | 232 |
On Representations of AlgebraicGeometric Codes for List Decoding | 244 |
Minimizing a Convex Cost Closure Set | 256 |
Preemptive Scheduling with Rejection | 268 |
Simpler and Faster VertexConnectivity Augmentation Algorithms | 278 |
Scheduling Broadcasts in Wireless Networks | 290 |
Jitter Regulation in an Internet Router with Delay Consideration | 302 |
Approximation of CurvatureConstrained Shortest Paths through a Sequence of Points | 314 |
Fast Algorithms for EvenOdd Minimum Cuts and Generalizations | 88 |
Efficient Algorithms for Centers and Medians in Interval and CircularArc Graphs | 100 |
Exact Point Pattern Matching and the Number of Congruent Triangles in a ThreeDimensional Pointset | 112 |
Range Searching over Tree Cross Products | 120 |
A 2frac110Approximation Algorithm for a Generalization of the Weighted EdgeDominating Set Problem | 132 |
The Minimum Range Assignment Problem on Linear Radio Networks Extended Abstract | 143 |
Property Testing in Computational Geometry05inExtended Abstract35in | 155 |
On RTrees with Low Stabbing Number | 167 |
KD Trees Are Better When Cut on the Longest Side | 179 |
On Multicriteria Online Problems | 191 |
Online Scheduling Revisited | 202 |
Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem | 211 |
IOEfficient WellSeparated Pair Decomposition and Its Applications Extended Abstract | 220 |
Resource Constrained Shortest Paths | 326 |
On the Competitiveness of Linear Search | 338 |
Maintaining a Minimum Spanning Tree under Transient Node Failures | 346 |
Minimum Depth Graph Embedding | 356 |
New Algorithms for TwoLabel Point Labeling | 368 |
Analysing the Cache Behaviour of Nonuniform Distribution Sorting Algorithms | 380 |
How Helpers Hasten hRelations | 392 |
Computing Optimal Linear Layouts of Trees in Linear Time | 403 |
Coloring Sparse Random Graphs in Polynomial Average Time | 415 |
Restarts Can Help in the OnLine Minimization of the Maximum Delivery Time on a Single Machine Extended Abstract | 427 |
Convexity Helps | 437 |
| 449 | |
Other editions - View all
Algorithms - ESA 2000: 8th Annual European Symposium Saarbrücken, Germany ... Michael S. Paterson No preview available - 2000 |
Algorithms - ESA 2000: 8th Annual European Symposium Saarbrücken, Germany ... Mike Paterson No preview available - 2000 |
Common terms and phrases
applications approximation algorithm assume biconnected block bounding boxes cache Cayley Cayley graphs coarse layout colored combinatorial complexity Computational Geometry Computer Science consider construction contains convex corresponding cost cycle data structure decomposition defined Delaunay triangulation denote digraph distance endpoint factor function geometric given graph drawing graph G Hence input integer intersect interval k-coloring k-d tree k-OD edge label Lemma linear LNCS lower bound machine matching maximal maximum Metafont minimizing minimum minimum cut Minkowski sum node NP-hard O(log objects offline on-line algorithm online algorithm optimal solution packets pair partition planar embedding planar graph point set polygons polynomial problem Proc Proof protein query query complexity R-tree radix sort random ratio rectangles requests rooted schedule Section sequence server shortest path solve space Springer-Verlag subset subtrees Theorem vertex vertices weight