Algorithm Theory — SWAT’98: 6th Scandinavian Workshop on Algorithm Theory Stockholm, Sweden, July 8–10, 1998 Proceedings

Andrew V. Goldberg (auth.), Stefan Arnborg, Lars Ivansson (eds.)3540646825, 9783540646822

This book constitutes the refereed proceedings of the 6th Scandinavian Workshop on Algorithm Theory, SWAT’98, held in Stockholm, Sweden, in July 1998.
The volume presents 28 revised full papers selected from 56 submissions; also included are three invited contributions. The papers present original research on algorithms and data structures in various areas including computational geometry, parallel and distributed systems, graph theory, approximation, computational biology, queueing, Voronoi diagrams, and combinatorics in general.

---

Table of contents :
Recent developments in maximum flow algorithms….Pages 1-10
An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces….Pages 11-22
Facility location with dynamic distance functions….Pages 23-34
An approximation scheme for bin packing with conflicts….Pages 35-46
Approximations for the general block distribution of a matrix….Pages 47-58
An optimal algorithm for computing visible nearest foreign neighbors among colored line segments….Pages 59-70
Moving an angle around a region….Pages 71-82
Models and motion planning….Pages 83-94
Constrained square-center problems….Pages 95-106
Worst-case efficient external-memory priority queues….Pages 107-118
Simple confluently persistent catenable lists….Pages 119-130
Improved upper bounds for time-space tradeoffs for selection with limited storage….Pages 131-142
Probabilistic data structures for priority queues….Pages 143-154
Extractors for weak random sources and their applications….Pages 155-157
Comparator networks for binary heap construction….Pages 158-168
Two-variable linear programming in parallel….Pages 169-180
Optimal deterministic protocols for mobile robots on a grid….Pages 181-192
Concurrent multicast in weighted networks….Pages 193-204
Some recent strong inapproximability results….Pages 205-209
Minimal elimination of planar graphs….Pages 210-221
Memory requirements for table computations in partial k -tree algorithms….Pages 222-233
Formal language constrained path problems….Pages 234-245
Local search algorithms for SAT: Worst-case analysis….Pages 246-254
Speed is more powerful than clairvoyance….Pages 255-263
Randomized online multi-threaded paging….Pages 264-275
Determinant: Old algorithms, new insights….Pages 276-287
Solving fundamental problems on sparse-meshes….Pages 288-299
Output-sensitive cell enumeration in hyperplane arrangements….Pages 300-309
Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology….Pages 310-321
On the number of regular vertices of the union of Jordan regions….Pages 322-334
Distribution-sensitive algorithms….Pages 335-346