Algorithms - ESA 2000

1. Front Matter

   Pages I-IX

   PDF

2. Invited Papers

   1. Web Information Retrieval - an Algorithmic Perspective

      • Monika Henzinger

      Pages 1-8

   2. Computational Biology — Algorithms and More

      • Thomas Lengauer

      Pages 9-19

3. Contributed Papers

   1. Polygon Decomposition for Efficient Construction of Minkowski Sums

      • Pankaj K. Agarwal, Eyal Flato, Dan Halperin

      Pages 20-31

   2. An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts

      • Alexander A. Ageev, Maxim I. Sviridenko

      Pages 32-41

   3. Offline List Update is NP-hard

      • Christoph Ambühl

      Pages 42-51

   4. Computing Largest Common Point Sets under Approximate Congruence

      • Christoph Ambühl, Samarjit Chakraborty, Bernd Gärtner

      Pages 52-64

   5. Online Algorithms for Caching Multimedia Streams

      • Matthew Andrews, Kamesh Munagala

      Pages 64-75

   6. On Recognizing Cayley Graphs

      • Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, Bernard Mans, John M. Robson

      Pages 76-87

   7. Fast Algorithms for Even/Odd Minimum Cuts and Generalizations

      • András A. Benczúr, Ottilia Fülöp

      Pages 88-99

   8. Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs

      • S. Bespamyatnikh, B. Bhattacharya, J. Mark Keil, D. Kirkpatrick, M. Segal

      Pages 100-112

   9. Exact Point Pattern Matching and the Number of Congruent Triangles in a Three-Dimensional Pointset

      • Peter Brass

      Pages 112-119

   10. Range Searching over Tree Cross Products

       • Adam L. Buchsbaum, Michael T. Goodrich, Jeffery R. Westbrook

       Pages 120-131

   11. A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem

       • Robert Carr, Toshihiro Fujito, Goran Konjevod, Ojas Parekh

       Pages 132-142

   12. The Minimum Range Assignment Problem on Linear Radio Networks

       • A. E. F. Clementi, A. Ferreira, P. Penna, S. Perennes, R. Silvestri

       Pages 143-154

   13. Property Testing in Computational Geometry

       • Artur Czumaj, Christian Sohler, Martin Ziegler

       Pages 155-166

   14. On R-Trees with Low Stabbing Number

       • Mark de Berg, Joachim Gudmundsson, Mikael Hammar, Mark Overmars

       Pages 167-178

   15. K-D Trees Are Better when Cut on the Longest Side

       • Matthew Dickerson, Christian A. Duncan, Michael T. Goodrich

       Pages 179-190

   16. On Multicriteria Online Problems

       • Michele Flammini, Gaia Nicosia

       Pages 191-201

   17. Online Scheduling Revisited

       • Rudolf Fleischer, Michaela Wahl

       Pages 202-210

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.

• Approximation
• Complexity
• Computational Geometry
• Computational Science
• Distributed AlgorithmsS
• Graph Algorithms
• Graph Computations
• On-line Algorithms
• Optimization
• Parallel Algorithms
• Randomization
• algorithms
• combinatorial optimization
• algorithm analysis and problem complexity
• data structures

• Department of Computer Science, University of Warwick, Coventry, UK

  Mike S. Paterson

Policies and ethics