Algorithm Theory — SWAT ’92: Third Scandinavian Workshop on Algorithm Theory Helsinki, Finland, July 8–10, 1992 Proceedings

Alexandras V. Gerbessiotis, Leslie G. Valiant (auth.), Otto Nurmi, Esko Ukkonen (eds.)3540557067, 9783540557067

The papers in this volume were presented at SWAT 92, the Third Scandinavian Workshop on Algorithm Theory. The workshop, which continues the tradition ofSWAT 88, SWAT 90, and the Workshop on Algorithms and Data Structures (WADS 89, WADS 91), is intended as an international forum for researchers in the area of design and analysis of algorithms. The volume contains invited papers by L.G. Valiant (Direct bulk-synchronous parallel algorithms), A.A. Razborov (On small depth threshold circuits), G. Gonnet (Efficient two-dimensional searching), and E. Welzl (New results on linear programming and related problems), together with 34 selected contributed papers. Contributions cover algorithms and data structures in all areas, including combinatorics, computational geometry, data bases, parallel and distributed computing, and graphics.

---

Table of contents :
Direct bulk-synchronous parallel algorithms….Pages 1-18
Memory limited inductive inference machines….Pages 19-29
Retrieval of scattered information by EREW, CREW and CRCW PRAMs….Pages 30-41
On small depth threshold circuits….Pages 42-52
An elementary approach to some analytic asymptotics….Pages 53-61
An optimal parallel algorithm for computing a near-optimal order of matrix multiplications….Pages 62-72
Generating sparse 2—spanners….Pages 73-82
Low-diameter graph decomposition is in NC….Pages 83-93
Parallel algorithm for cograph recognition with applications….Pages 94-105
Parallel algorithms for all minimum link paths and link center problems….Pages 106-117
Optimal multi-packet routing on the torus….Pages 118-129
Parallel algorithms for priority queue operations….Pages 130-139
Heap construction in the parallel comparison tree model….Pages 140-150
Efficient rebalancing of chromatic search trees….Pages 151-164
The complexity of scheduling problems with communication delays for trees….Pages 165-177
The list update problem and the retrieval of sets….Pages 178-191
Gkd-trees: Binary trees that combine multi-dimensional data handling, node size and fringe reorganization….Pages 192-211
Fractional cascading simplified….Pages 212-220
Dynamic 2- and 3-connectivity on planar graphs….Pages 221-232
Fully dynamic 2-edge-connectivity in planar graphs….Pages 233-244
Non-interfering network flows….Pages 245-257
Triangulating planar graphs while minimizing the maximum degree….Pages 258-271
How to draw a series-parallel digraph….Pages 272-283
Coloring random graphs….Pages 284-291
Testing superperfection of k -trees….Pages 292-303
Parametric problems on graphs of bounded tree-width….Pages 304-316
Efficient two-dimensional searching….Pages 317-317
Improvements on geometric pattern matching problems….Pages 318-325
Determining DNA sequence similarity using maximum independent set algorithms for interval graphs….Pages 326-337
New results on linear programming and related problems….Pages 338-339
Dynamic closest pairs — A probabilistic approach….Pages 340-351
Two- and three- dimensional point location in rectangular subdivisions….Pages 352-363
Decomposing the boundary of a nonconvex polyhedron….Pages 364-375
Convex polygons made from few lines and convex decompositions of polyhedra….Pages 376-387
Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity….Pages 388-398
Voronoi diagrams of moving points in higher dimensional spaces….Pages 399-409
Sorting multisets stably in minimum space….Pages 410-421
A framework for adaptive sorting….Pages 422-433