SWAT 88: 1st Scandinavian Workshop on Algorithm Theory Halmstad, Sweden, July 5–8, 1988 Proceedings

An implicit binomial queue with constant insertion time....Pages 1-13
Implicit selection....Pages 14-23
An extrapolation on the interpolation search....Pages 24-33
Time parameter and arbitrary deunions in the set union problem....Pages 34-42
Two new algorithms for constructing min-max heaps....Pages 43-50
Extremal cost tree data structures....Pages 51-63
Intersecting line segments, ray shooting, and other applications of geometric partitioning techniques....Pages 64-73
Problems of posting sentries: Variations on the art gallery theorem....Pages 74-85
A lower bound and two approximative algorithms for the K-partitioning of rectilinear polygons....Pages 86-95
On recognizing and characterizing visibility graphs of simple polygons....Pages 96-104
Connectability problems....Pages 105-112
Two hybrid methods for collision resolution in open addressing hashing....Pages 113-119
On an alternative sum useful in the analysis of some data structures....Pages 120-128
Bin-packing in 1.5 dimension....Pages 129-137
Applications of a symbolic perturbation scheme....Pages 138-138
A fast parallel algorithm for computing all maximal cliques in a graph and the related problems....Pages 139-144
Parallel solution of sparse linear systems....Pages 145-153
A note on determining the 3-dimensional convex hull of a set of points on a mesh of processors....Pages 154-162
Probabilistic log-space reductions and problems probabilistically hard for p....Pages 163-175
Searching with uncertainty extended abstract....Pages 176-189
An optimal expected-time parallel algorithm for Voronoi diagrams....Pages 190-198
Generating binary trees by transpositions....Pages 199-207
Approximating the complete Euclidean graph....Pages 208-213
Upper and lower bounds for the dictionary problem....Pages 214-215
Linear algorithms for graph separation problems....Pages 216-222
Polynomial algorithms for graph isomorphism and chromatic index on partial k -trees....Pages 223-232
NC algorithms for computing the number of perfect matchings in K 3,3 -free graphs and related problems....Pages 233-242
Independent covers in outerplanar graphs....Pages 243-254
Tight lower bounds for Shellsort....Pages 255-262