Algorithm Theory - SWAT '94

Computing depth orders and related problems.- Selection in monotone matrices and computing k th nearest neighbors.- New on-line algorithms for the page replication problem.- Serving requests with on-line routing.- A new algorithm for the construction of optimal B-trees.- New results on binary space partitions in the plane (extended abstract).- A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon.- On triangulating planar graphs under the four-connectivity constraint.- Parallel and sequential approximation of shortest superstrings.- Separating translates in the plane: Combinatorial bounds and an algorithm.- Finding all weakly-visible chords of a polygon in linear time.- A tight lower bound for on-line monotonic list labeling.- Trapezoid graphs and generalizations, geometry and algorithms.- Optimal parametric search on graphs of bounded tree-width.- Lower bounds for dynamic algorithms.- Sequential and parallel algorithms for embedding problems on classes of partial k-trees.- On intersection searching problems involving curved objects.- Improved approximations of independent sets in bounded-degree graphs.- Asymptotically optimal election on weighted rings.- Optimal algorithms for broadcast and gossip in the edge-disjoint path modes.- Recent results in hardness of approximation.- The parallel hierarchical memory model.- Randomized geometric algorithms (abstract).- Connecting the maximum number of grid nodes to the boundary with non-intersecting line segments.- On self-stabilizing wait-free clock synchronization.- Hard graphs for randomized subgraph exclusion algorithms.- Task scheduling in networks.- Parallel dynamic lowest common ancestors.- An O(log log n) algorithm to compute the kernel of a polygon.- Computing the L 1-diameter and center of a simple rectilinear polygon in parallel.- Exploiting locality in LT-RAM computations.- Efficient preprocessing of simple binary pattern forests.- A parallel algorithm for edge-coloring partial k-trees.- Dominating cliques in distance-hereditary graphs.