Algorithms and Data Structures: 2nd Workshop, WADS ’91 Ottawa, Canada, August 14–16, 1991 Proceedings

Walter Cunto, J. Ian Munro, Patricio V. Poblete (auth.), Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro (eds.)3540543430, 9783540543435

This volume presents the proceedings of the Second Workshop on Algorithms and Data Structures (WADS ’91), held at Carleton University in Ottawa. The workshop was organized by the School of Computer Science at Carleton University. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the tradition of SWAT ’88 (LNCS, Vol. 318), WADS ’89 (LNCS, Vol. 382), and SWAT ’90 (LNCS, Vol. 447). From 107 papers submitted, 37 were selected for presentation at the workshop. In addition, there were 5 invited presentations.

---

Table of contents :
A case study in comparison based complexity: Finding the nearest value(s)….Pages 1-12
On the zone of a surface in a hyperplane arrangement….Pages 13-19
Ray-shooting and isotopy classes of lines in 3-dimensional space….Pages 20-31
Finding level-ancestors in dynamic trees….Pages 32-40
Treewidth of circular-arc graphs+….Pages 41-41
Fully dynamic delaunay triangulation in logarithmic expected time per operation….Pages 42-53
On computing the voronoi diagram for restricted planar figures….Pages 54-64
The MINSUMCUT problem….Pages 65-79
Efficient algorithms for the minimum range cut problems….Pages 80-91
Memory access in models of parallel computation: From folklore to synergy and beyond….Pages 92-104
Farthest neighbors, maximum spanning trees and related problems in higher dimensions….Pages 105-116
Shallow interdistance selection and interdistance enumeration….Pages 117-128
Sharing memory in asynchronous message passing systems….Pages 129-140
A linear-time scheme for version reconstruction….Pages 141-152
The interval skip list: A data structure for finding all intervals that overlap a point….Pages 153-164
Geometric knapsack problems….Pages 165-176
A fast derandomization scheme and its applications….Pages 177-188
Unstructured path problems and the making of semirings….Pages 189-200
Neighborhood graphs and geometric embedding….Pages 201-201
Finding optimal bipartitions of points and polygons….Pages 202-213
Immobilizing a polytope….Pages 214-227
What can we learn about suffix trees from independent tries?….Pages 228-239
Competitive algorithms for the weighted list update problem….Pages 240-248
An optimal algorithm for the rectilinear link center of a rectilinear polygon….Pages 249-260
Geometric searching and link distance….Pages 261-272
Representing and enumerating edge connectivity cuts in RNC ….Pages 273-285
Planar graph augmentation problems….Pages 286-298
Parametric search and locating supply centers in trees….Pages 299-319
On bends and lengths of rectilinear paths: A graph-theoretic approach….Pages 320-330
Computing minimum length paths of a given homotopy class….Pages 331-342
Approximation algorithms for selecting network centers….Pages 343-354
Facility dispersion problems: Heuristics and special cases….Pages 355-366
Optimum guard covers and m -watchmen routes for restricted polygons….Pages 367-378
Applications of a new space partitioning technique….Pages 379-391
Offline algorithms for dynamic minimum spanning tree problems….Pages 392-399
An empirical analysis of algorithms for constructing a minimum spanning tree….Pages 400-411
A linear time algorithm for computing the shortest line segment from which a polygon is weakly externally visible….Pages 412-424
Dynamically maintaining the visibility graph….Pages 425-436
An optimal algorithm for computing visibility in the plane….Pages 437-448
Fully persistent data structures for disjoint set union problems….Pages 449-460
Algorithms for generating all spanning trees of undirected, directed and weighted graphs….Pages 461-472
Sorting multisets and vectors in-place….Pages 473-480
Probabilistic leader election on rings of known size….Pages 481-495