Algorithm Theory - SWAT'98: 6th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, July 8-10, 1998, Proceedings (Lecture Notes in Computer Science (1432))

Annotation 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 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

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.

The maximum flow problem is a classical optimization problem with many applications; see e.g. [1, 18, 39].