Beschreibung
InhaltsangabeAn implicit binomial queue with constant insertion time.- Implicit selection.- An extrapolation on the interpolation search.- Time parameter and arbitrary deunions in the set union problem.- Two new algorithms for constructing min-max heaps.- Extremal cost tree data structures.- Intersecting line segments, ray shooting, and other applications of geometric partitioning techniques.- Problems of posting sentries: Variations on the art gallery theorem.- A lower bound and two approximative algorithms for the K-partitioning of rectilinear polygons.- On recognizing and characterizing visibility graphs of simple polygons.- Connectability problems.- Two hybrid methods for collision resolution in open addressing hashing.- On an alternative sum useful in the analysis of some data structures.- Bin-packing in 1.5 dimension.- Applications of a symbolic perturbation scheme.- A fast parallel algorithm for computing all maximal cliques in a graph and the related problems.- Parallel solution of sparse linear systems.- A note on determining the 3-dimensional convex hull of a set of points on a mesh of processors.- Probabilistic log-space reductions and problems probabilistically hard for p.- Searching with uncertainty extended abstract.- An optimal expected-time parallel algorithm for Voronoi diagrams.- Generating binary trees by transpositions.- Approximating the complete Euclidean graph.- Upper and lower bounds for the dictionary problem.- Linear algorithms for graph separation problems.- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees.- NC algorithms for computing the number of perfect matchings in K 3,3-free graphs and related problems.- Independent covers in outerplanar graphs.- Tight lower bounds for Shellsort.
