8. ESA 2000: Saarbrücken, Germany

Invited Papers

• Monika Rauch Henzinger:
  Web Information Retrieval - an Algorithmic Perspective. 1-8
  
• Thomas Lengauer:
  Computational Biology - Algorithms and More. 9-19
  

Contributed Papers

• Pankaj K. Agarwal, Eyal Flato, Dan Halperin:
  Polygon Decomposition for Efficient Construction of Minkowski Sums. 20-31
  
• Alexander A. Ageev, Maxim Sviridenko:
  An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts. 32-41
  
• Christoph Ambühl:
  Offline List Update is NP-Hard. 42-51
  
• Christoph Ambühl, Samarjit Chakraborty, Bernd Gärtner:
  Computing Largest Common Point Sets under Approximate Congruence. 52-63
  
• Matthew Andrews, Kamesh Munagala:
  Online Algorithms for Caching Multimedia Streams. 64-75
  
• Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, Bernard Mans, John Michael Robson:
  On Recognizing Cayley Graphs. 76-87
  
• András A. Benczúr, Ottilia Fülöp:
  Fast Algorithms for Even/Odd Minimum Cuts and Generalizations. 88-99
  
• Sergei Bespamyatnikh, Binay K. Bhattacharya, J. Mark Keil, David G. Kirkpatrick, Michael Segal:
  Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs. 100-111
  
• Peter Brass:
  Exact Point Pattern Matching and the Number of Congruent Triangles in a Three-Dimensional Pointset. 112-119
  
• Adam L. Buchsbaum, Michael T. Goodrich, Jeffery Westbrook:
  Range Searching Over Tree Cross Products. 120-131
  
• Robert D. Carr, Toshihiro Fujito, Goran Konjevod, Ojas Parekh:
  A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem. 132-142
  
• Andrea E. F. Clementi, Afonso Ferreira, Paolo Penna, Stephane Perennes, Riccardo Silvestri:
  The Minimum Range Assignment Problem on Linear Radio Networks. 143-154
  
• Artur Czumaj, Christian Sohler, Martin Ziegler:
  Property Testing in Computational Geometry. 155-166
  
• Mark de Berg, Joachim Gudmundsson, Mikael Hammar, Mark H. Overmars:
  On R-trees with Low Stabbing Number. 167-178
  
• Matthew Dickerson, Christian A. Duncan, Michael T. Goodrich:
  K-D Trees Are Better when Cut on the Longest Side. 179-190
  
• Michele Flammini, Gaia Nicosia:
  On Multicriteria Online Problems. 191-201
  
• Rudolf Fleischer, Michaela Wahl:
  Online Scheduling Revisited. 202-210
  
• Daya Ram Gaur, Toshihide Ibaraki, Ramesh Krishnamurti:
  Constan Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem. 211-219
  
• Sathish Govindarajan, Tamás Lukovszki, Anil Maheshwari, Norbert Zeh:
  I/O-Efficient Well-Separated Pair Decomposition and Its Applications. 220-231
  
• Joachim Gudmundsson, Mikael Hammar, Marc J. van Kreveld:
  Higher Order Delaunay Triangulations. 232-243
  
• Venkatesan Guruswami, Madhu Sudan:
  On Representations of Algebraic-Geometric Codes for List Decoding. 244-255
  
• Dorit S. Hochbaum, Maurice Queyranne:
  Minimizing a Convex Cost Closure Set. 256-267
  
• Han Hoogeveen, Martin Skutella, Gerhard J. Woeginger:
  Preemptive Scheduling with Rejection. 268-277
  
• Tsan-sheng Hsu:
  Simpler and Faster Vertex-Connectivity Augmentation Algorithms. 278-289
  
• Bala Kalyanasundaram, Kirk Pruhs, Mahendran Velauthapillai:
  Scheduling Broadcasts in Wireless Networks. 290-301
  
• Hisashi Koga:
  Jitter Regulation in an Internet Router with Delay Consideration. 302-313
  
• Jae-Ha Lee, Otfried Cheong, Woo-Cheol Kwon, Sung Yong Shin, Kyung-Yong Chwa:
  Approximation of Curvature-Constrained Shortest Paths through a Sequence of Points. 314-325
  
• Kurt Mehlhorn, Mark Ziegelmann:
  Resource Constrained Shortest Paths. 326-337
  
• J. Ian Munro:
  On the Competitiveness of Linear Search. 338-345
  
• Enrico Nardelli, Guido Proietti, Peter Widmayer:
  Maintaining a Minimum Spanning Tree Under Transient Node Failures. 346-355
  
• Maurizio Pizzonia, Roberto Tamassia:
  Minimum Depth Graph Embedding. 356-367
  
• Zhongping Qin, Alexander Wolff, Yin-Feng Xu, Binhai Zhu:
  New Algorithms for Two-Label Point Labeling. 368-379
  
• Naila Rahman, Rajeev Raman:
  Analysing the Cache Behaviour of Non-uniform Distribution Sorting Algorithms. 380-391
  
• Peter Sanders, Roberto Solis-Oba:
  How Helpers Hasten h-Relations. 392-402
  
• Konstantin Skodinis:
  Computing Optimal Linear Layouts of Trees in Linear Time. 403-414
  
• C. R. Subramanian:
  Coloring Sparse Random Graphs in Polynominal Average Time. 415-426
  
• Marjan van den Akker, Han Hoogeveen, Nodari Vakhania:
  Restarts Can Help in the On-Line Minimization of the Maximum Delivery Time on a Single Machine. 427-436
  
• Yunhong Zhou, Subhash Suri:
  Collision Detection Using Bounding Boxes: Convexity Helps. 437-448