Algorithm Theory — SWAT ’94: 4th Scandinavian Workshop on Algorithm Theory Aarhus, Denmark, July 6–8, 1994 Proceedings

Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir (auth.), Erik M. Schmidt, Sven Skyum (eds.)3540582185, 9783540582182

This volume constitutes the proceedings of SWAT ’94, the 4th Scandinavian Workshop on Algorithm Theory, held in Aarhus, Denmark in July 1994. The SWAT events are organized each even year and alternate with the WADS meetings (Workshops on Algorithms and Data Structures) held each odd year in North America.
The volume contains 31 papers selected from a total of 100 submissions and 3 invited presentations by Michael Fredman (Rutgers), Johan Hastad (Stockholm), and Ketan Mulmuley (Chicago). The contributions cover algorithms and data structures in all areas of computer science and in discrete mathematics, particularly including graph theory, computational geometry, and databases.

---

Table of contents :
Computing depth orders and related problems….Pages 1-12
Selection in monotone matrices and computing k th nearest neighbors….Pages 13-24
New on-line algorithms for the page replication problem….Pages 25-36
Serving requests with on-line routing….Pages 37-48
A new algorithm for the construction of optimal B-trees….Pages 49-60
New results on binary space partitions in the plane (extended abstract)….Pages 61-72
A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon….Pages 73-82
On triangulating planar graphs under the four-connectivity constraint….Pages 83-94
Parallel and sequential approximation of shortest superstrings….Pages 95-106
Separating translates in the plane: Combinatorial bounds and an algorithm….Pages 107-118
Finding all weakly-visible chords of a polygon in linear time….Pages 119-130
A tight lower bound for on-line monotonic list labeling….Pages 131-142
Trapezoid graphs and generalizations, geometry and algorithms….Pages 143-154
Optimal parametric search on graphs of bounded tree-width….Pages 155-166
Lower bounds for dynamic algorithms….Pages 167-171
Sequential and parallel algorithms for embedding problems on classes of partial k -trees….Pages 172-182
On intersection searching problems involving curved objects….Pages 183-194
Improved approximations of independent sets in bounded-degree graphs….Pages 195-206
Asymptotically optimal election on weighted rings….Pages 207-218
Optimal algorithms for broadcast and gossip in the edge-disjoint path modes….Pages 219-230
Recent results in hardness of approximation….Pages 231-239
The parallel hierarchical memory model….Pages 240-251
Randomized geometric algorithms (abstract)….Pages 252-254
Connecting the maximum number of grid nodes to the boundary with non-intersecting line segments….Pages 255-266
On self-stabilizing wait-free clock synchronization….Pages 267-277
Hard graphs for randomized subgraph exclusion algorithms….Pages 278-289
Task scheduling in networks….Pages 290-301
Parallel dynamic lowest common ancestors….Pages 302-313
An O (log log n ) algorithm to compute the kernel of a polygon….Pages 314-325
Computing the L 1 -diameter and center of a simple rectilinear polygon in parallel….Pages 326-337
Exploiting locality in LT-RAM computations….Pages 338-349
Efficient preprocessing of simple binary pattern forests….Pages 350-358
A parallel algorithm for edge-coloring partial k -trees….Pages 359-369
Dominating cliques in distance-hereditary graphs….Pages 370-381