Algorithms and Data Structures

Computing the all-pairs longest chains in the plane.- Towards a better understanding of pure packet routing.- Tolerating faults in meshes and other networks.- A generalization of binary search.- Groups and algebraic complexity.- Connected component and simple polygon intersection searching.- An optimal algorithm for finding the separation of simple polygons.- Balanced search trees made simple.- Probing a set of hyperplanes by lines and related problems.- A general lower bound on the I/O-complexity of comparison-based algorithms.- Point probe decision trees for geometric concept classes.- A dynamic separator algorithm.- Online load balancing of temporary tasks.- Connected domination and steiner set on asteroidal triple-free graphs.- The complexity of finding certain trees in tournaments.- Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract).- Separating the power of EREW and CREW PRAMs with small communication width.- Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs.- Parallel construction of quadtrees and quality triangulations.- Pattern matching for permutations.- Filling polyhedral molds.- Deferred-query-An efficient approach for problems on interval and circular-arc graphs.- On the complexity of graph embeddings.- Algorithms for polytope covering and approximation.- Global strategies for augmenting the efficiency of TSP heuristics.- Static and dynamic algorithms for k-point clustering problems.- Scalable algorithms for bichromatic line segment intersection problems on Coarse Grained Multicomputers.- Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract).- The K-D heap: An efficient multi-dimensional priority queue.- A complete and efficient algorithm for the intersection of a general and a convex polyhedron.- Computing the smallest k-enclosing circle and related problems.- An