Algorithms: International Symposium SIGAL '90, Tokyo, Japan, August 16-18, 1990. Proceedings

ISBN-13: 9783540529217 / Angielski / Miękka / 1990 / 482 str.

Tetsuo Asano;Toshihide Ibaraki;Hiroshi Imai

Opis

This is the proceedings of the SIGAL International Symposium on Algorithms held at CSK Information Education Center, Tokyo, Japan, August 16-18, 1990. SIGAL (Special Interest Group on Algorithms) was organized within the Information Processing Society of Japan in 1988 to encourage research in the field of discrete algorithms, and held 6-8 research meetings each year.

Spis treści

Recent progress in string algorithms.- Selection networks.- Computing edge-connectivity in multiple and capacitated graphs.- Efficient sequential and parallel algorithms for planar minimum cost flow.- Structural analyses on the complexity of inverting functions.- Oracles versus proof techniques that do not relativize.- 20-Relative neighborhood graphs are Hamiltonian.- The K-Gabriel graphs and their applications.- Parallel algorithms for generating subsets and set partitions.- Parallel algorithms for linked list and beyond.- Local tournaments and proper circular arc graphs.- Fast algorithms for the dominating set problem on permutation graphs.- Two probabilistic results on merging.- Randomized broadcast in networks.- On the construction of abstract voronoi diagrams, II.- Searching in higher dimension.- Finding extrema with unary predicates.- Implicitly searching convolutions and computing depth of collision.- Characterization for a family of infinitely many irreducible Equally Spaced Polynomials.- Distributed algorithms for deciphering.- An efficient algorithm for optimal loop parallelization (extended abstract).- Another view on the SSS* algorithm.- Algorithms from complexity theory: Polynomial-time operations for complex sets.- Complexity cores and hard problem instances.- Spatial point location and its applications.- Sublinear merging and natural merge sort.- Constructing strongly convex approximate hulls with inaccurate primitives.- Computing puiseux-series solutions to determinatal equations via combinatorial relaxation.- A tight lower bound on the size of planar permutation networks.- Simultaneous solution of families of problems.- Algorithms for projecting points to give the most uniform distribution with applications to hashing.- Topological sweeping in three dimensions.- Finding least-weight subsequences with fewer processors.- Derandomization by exploiting redundancy and mutual independence.- Planar separators and the Euclidean norm.- On the complexity of isometric embedding in the hypercube.- Distributed function evaluation in the presence of transmission faults.- Optimal linear broadcast.- Graph augmentation problems for a specified set of vertices.- A heuristic algorithm for the k-center problem with vertex weight.- Parallel convexity algorithms for digitized images on a linear array of processors.- Parallel algorithms for labeling image components.- A hyperplane Incidence problem with applications to counting distances.- Splitting a configuration in a simplex.- Weaving patterns of lines and line segments in space.- Efficient parallel algorithms for path problems in planar directed graphs.- Parallel algorithms for finding Steiner forests in planar graphs.- Optimally managing the history of an evolving forest.