Algorithms - ESA 2000: 8th Annual European Symposium Saarbrücken, Germany, September 5–8, 2000 ProceedingsAuthor: Mike S. Paterson Published by Springer Berlin Heidelberg ISBN: 978-3-540-41004-1 DOI: 10.1007/3-540-45253-2Table of Contents:Web Information Retrieval - an Algorithmic Perspective Computational Biology — Algorithms and More Polygon Decomposition for Efficient Construction of Minkowski Sums An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts Offline List Update is NP-hard Computing Largest Common Point Sets under Approximate Congruence Online Algorithms for Caching Multimedia Streams On Recognizing Cayley Graphs Fast Algorithms for Even/Odd Minimum Cuts and Generalizations Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs Exact Point Pattern Matching and the Number of Congruent Triangles in a Three-Dimensional Pointset Range Searching over Tree Cross Products A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem The Minimum Range Assignment Problem on Linear Radio Networks Property Testing in Computational Geometry On R-Trees with Low Stabbing Number K-D Trees Are Better when Cut on the Longest Side On Multicriteria Online Problems Online Scheduling Revisited Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem, Includes bibliographical references and index, Web Information Retrieval -- an Algorithmic Perspective / Monika Henzinger -- Computational Biology -- Algorithms and More / Thomas Lengauer -- Polygon Decomposition for Efficient Construction of Minkowski Sums / Pankaj K. Agarwal, Eyal Flato and Dan Halperin -- An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts / Alexander A. Ageev and Maxim I. Sviridenko -- Offline List Update Is NP-Hard / Christoph Ambuhl -- Computing Largest Common Point Sets under Approximate Congruence / Christoph Ambuhl, Samarjit Chakraborty and Bernd Gartner -- Online Algorithms for Caching Multimedia Streams / Matthew Andrews and Kamesh Munagala -- On Recognizing Cayley Graphs / Lali Barriere, Pierre Fraigniaud and Cyril Gavoille / [et al.] -- Fast Algorithms for Even/Odd Minimum Cuts and Generalizations / Andras A. Benczur and Ottilia Fulop -- Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs / S. Besparnyatnikh, B. Bhattacharya and J. Mark Keil / [et al.] -- Exact Point Pattern Matching and the Number of Congruent Triangles in a Three-Dimensional Pointset / Peter Brass -- Range Searching Over Tree Cross Products / Adam L. Buchsbaum, Michael T. Goodrich and Jeffery R. Westbrook -- A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem / Robert Carr, Toshihiro Fujito and Goran Konjevod / [et al.] -- The Minimum Range Assignment Problem on Linear Radio Networks / A. E. F. Clementi, A. Ferreira and P. Penna / [et al.] -- Property Testing in Computational Geometry / Artur Czumaj, Christian Sohler and Martin Ziegler -- On R-trees with Low Stabbing Number / Mark de Berg, Joachim Gudmundsson and Mikael Hammar / [et al.] -- K-D Trees Are Better when Cut on the Longest Side / Matthew Dickerson, Christian A. Duncan and Michael T. Goodrich -- On Multicriteria Online Problems / Michele Flammini and Gaia Nicosia -- Online Scheduling Revisited / Rudolf Fleischer and Michaela Wahl -- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem / Daya Ram Gaur, Toshihide Ibaraki and Ramesh Krishnamurti -- I/O-Efficient Well-Separated Pair Decomposition and Its Applications / Sathish Govindarajan, Tamas Lukovszki and Anil Maheshwari / [et al.] -- Higher Order Delaunay Triangulations / Joachim Gudmundsson, Mikael Hammar and Marc van Kreveld -- On Representations of Algebraic-Geometric Codes for List Decoding / Venkatesan Guruswami and Madhu Sudan -- Minimizing a Convex Cost Closure Set / Dorit S. Hochbaum and Maurice Queyranne -- Preemptive Scheduling with Rejection / Han Hoogeveen, Martin Skutella and Gerhard J. Woeginger -- Simpler and Faster Vertex-Connectivity Augmentation Algorithms / Tsan-sheng Hsu -- Scheduling Broadcasts in Wireless Networks / Bala Kalyanasundaram, Kirk Pruhs and Mahe Velauthapillai -- Jitter Regulation in an Internet Router with Delay Consideration / Hisashi Koga -- Approximation in Curvature-Constrained Shortest Paths through a Sequence of Points / Jae-Ha Lee, Otfried Cheong and Woo-Cheol Kwon / [et al.] -- Resource Constrained Shortest Paths / Kurt Mehlhorn and Mark Ziegelmann -- On the Competitiveness of Linear Search / J. Ian Munro -- Maintaining a Minimum Spanning Tree Under Transient Node Failures / Enrico Nardelli, Guido Proietti and Peter Widmayer -- Minimum Depth Graph Embedding / Maurizio Pizzonia and Roberto Tamassia -- New Algorithms for Two-Label Point Labeling / Zhongping Qin, Alexander Wolff and Yinfeng Xu / [et al.] -- Analysing the Cache Behaviour of Non-uniform Distribution Sorting Algorithms / Naila Rahman and Rajeev Raman -- How Helpers Hasten h-Relations / Peter Sanders and Roberto Solis-Oba -- Computing Optimal Linear Layouts of Trees in Linear Time / Konstantin Skodinis -- Coloring Sparse Random Graphs in Polynomial Average Time / C. R. Subramanian -- Restarts Can Help in the On-Line Minimization of the Maximum Delivery Time on a Single Machine / Marjan van den Akker, Han Hoogeveen and Nodari Vakhania -- Collision Detection Using Bounding Boxes: Convexity Helps / Yunhong Zhou and Subhash Suri