Algorithm Theory - SWAT'98: 6th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, July 8-10, 1998, Proceedings

by S. Arnborg (Editor)

Recent developments in maximum flow algorithms.- An ? - Approximation algorithm for weighted shortest paths on polyhedral surfaces.- Facility location with dynamic distance functions.- An approximation scheme for bin packing with conflicts.- Approximations for the general block distribution of a matrix.- An optimal algorithm for computing visible nearest foreign neighbors among colored line segments.- Moving an angle around a region.- Models and motion planning.- Constrained square-center problems.- Worst-case efficient external-memory priority queues.- Simple confluently persistent catenable lists.- Improved upper bounds for time-space tradeoffs for selection with limited storage.- Probabilistic data structures for priority queues.- Extractors for weak random sources and their applications.- Comparator networks for binary heap construction.- Two-variable linear programming in parallel.- Optimal deterministic protocols for mobile robots on a grid.- Concurrent multicast in weighted networks.- Some recent strong inapproximability results.- Minimal elimination of planar graphs.- Memory requirements for table computations in partial k-tree algorithms.- Formal language constrained path problems.- Local search algorithms for Worst-case analysis.- Speed is more powerful than clairvoyance.- Randomized online multi-threaded paging.- Old algorithms, new insights.- Solving fundamental problems on sparse-meshes.- Output-sensitive cell enumeration in hyperplane arrangements.- Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology.- On the number of regular vertices of the union of Jordan regions.- Distribution-sensitive algorithms.

364 pages, Paperback

First published June 24, 1998