Algorithms and Data Structures

Lower bounds to processor-time tradeoffs under bounded-speed message propagation.- The two-line center problem from a polar view: a new algorithm and data structure.- On some geometric selection and optimization problems via sorted matrices.- Load balancing in quorum systems.- Balanced distributed search trees do not exist.- Two-floodlight illumination of convex polygons.- On the complexity of approximating and illuminating three-dimensional convex polyhedra.- Scheduling jobs that arrive over time.- Dynamic algorithms for the Dyck languages.- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications.- Computing a shortest watchman path in a simple polygon in polynomial-time.- Going home through an unknown street.- Page migration with limited local memory capacity.- Randomized algorithms for metrical task systems.- Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC-machining.- Computing common tangents without a separating line.- Online perfect matching and mobile computing.- Competitive algorithms for the on-line traveling salesman.- Quadrangulations of planar sets.- A linear-time construction of the relative neighborhood graph within a histogram.- Computing proximity drawings of trees in the 3-dimensional space.- Routing on trees via matchings.- A ranking algorithm for Hamilton paths in shuffle-exchange graphs.- Amortization results for chromatic search trees, with an application to priority queues.- Fast meldable priority queues.- On the computation of fast data transmissions in networks with capacities and delays.- Routing with delays when storage is costly.- Algorithmic arguments in physics of computation.- The buffer tree: A new technique for optimal I/O-algorithms.- Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep.- Computing a dominating pair in an asteroidal triple-free graph in linear time.- A linear algorithm for the maximal planar subgraph problem.- Topology B-trees and their applications.- In-place calculation of minimum-redundancy codes.- Regular-factors in the complements of partial k-trees.- Obstructions to within a few vertices or edges of acyclic.- Faster enumeration of all spanning trees of a directed graph.- A simpler minimum spanning tree verification algorithm.- On approximation properties of the Independent set problem for degree 3 graphs.- Approximation of Constraint Satisfaction via local search.- On the difficulty of range searching.- Tables should be sorted (on random access machines).- Improved length bounds for the shortest superstring problem.- Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles).- Experiences with the implementation of geometric algorithms.