ESA - accepted papers

[Mike Paterson]

List of papers accepted for ESA 2000 (Saarbruecken, Sept 5-8)
=============================================================

Polygon Decomposition for Efficient Construction of Minkowski Sums
     --- Pankaj K. Agarwal and 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 Ambuehl

Computing the LCP of two Point Sets under Approximate Congruence
     --- Christoph Ambuehl and Samarjit Chakraborty and Bernd Gaertner

Online Algorithms for Caching Multimedia Streams
     --- Matthew Andrews and Kamesh Munagala

On Recognizing Cayley Graphs
     --- Lali Barriere and Pierre Fraigniaud and Cyril Gavoille and Bernard

Fast algorithms for even/odd minimum cuts and generalizations
     --- Andras A. Benczur and Otilia Fulop

Efficient algorithms for centers and medians in interval and
     --- S. Bespamyatnikh and B. Bhattacharya and J. Mark Keil and D.

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 and 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 and Toshihiro Fujito and Goran Konjevod and Ojas Parekh

The Minimum Range Assignment Problem on Linear Radio Networks
     --- A.E.F. Clementi, A. Ferreira, P. Penna, S. Perennes and R. Silvestri

Property Testing in Computational Geometry
     --- Artur Czumaj and Christian Sohler and Martin Ziegler

On R-trees with low stabbing number
     --- M. de Berg, J. Gudmundsson, M. Hammar, M. Overmars

K-D Trees are Better When Cut on the Longest Side
     --- Matthew Dickerson and Christian A. Duncan and Michael T. Goodrich

On multicriteria online problems
     --- M. Flammini and G. Nicosia

Online scheduling
     --- Rudolf Fleischer and Michaela Wahl

Constant ratio approximation algorithms for the rectangle
     --- Daya Ram Gaur and Toshihide Ibaraki and Ramesh Krishnamurti

Almost Delaunay triangulation
     --- J. Gudmundsson and M. Hammar and M. van K

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
     --- H. Hoogeveen, M. Skutella, G.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 of Curvature-constrained Shortest Paths through a Sequence 
	of Points
     --- Jae-Ha Lee, Otfried Cheong, Woo-Cheol Kwon, Sung Yong Shin 
	and Kyung-Yong Chwa

I/O-Efficient Well-Separated Pair Decomposition and its Applications
     --- Tamas Lukovszki and Anil Maheshwari and Norbert Zeh

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 and Alexander Wolff and Yinfeng Xu and Binhai Zhu

Analyzing 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
     --- J.M. van den Akker and J.A. Hoogeveen and N. Vakhania

Collision Detection Using Bounding Boxes: Convexity Helps
     --- Yunhong Zhou and Subhash Suri


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/maillist.html.