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: Anefficient 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 index data structure for matrices, with applications to fast two-dimensional pattern matching.- A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects.- Further results on generalized intersection searching problems: Counting, reporting, and dynamization.- Generalized approximate algorithms for point set congruence.- Approximating shortest superstrings with constraints.- Tree reconstruction from partial orders.- Improved parallel depth-first search in undirected planar graphs.- On approximating the longest path in a graph.- Designing multi-commodity flow trees.- A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs.- On fat partitioning, fat covering and the union size of polygons.- A time-randomness tradeoff for selection in parallel.- Detecting race conditions in parallel programs that use one semaphore.- An algorithm for finding predecessors in integer sets.- The exhaustion of shared memory: Stochastic results.- Minimum weight euclidean matching and weighted relative neighborhood graphs.- Efficient approximate shortest-path queries among isothetic rectangular obstacles.- Counting and reporting red/blue segment intersections.- Repetitive hidden-surface-removal for polyhedral scenes.- On reconfigurability of VLSI linear arrays.- Reconstructing strings from substrings (Extended abstract).- Combinatorial complexity of signed discs.- Fast algorithms for one-dimensionsal compaction with jog insertion.- An optimal algorithm for roundness determination on convex polygons.- Practical algorithms on partial k-trees with an application to domination-like problems.- Greedy algorithms for the on-line steiner tree and generalized steiner problems.