Algorithms: International Symposium SIGAL ’90 Tokyo, Japan, August 16–18, 1990 Proceedings

Zvi Galil (auth.), Tetsuo Asano, Toshihide Ibaraki, Hiroshi Imai, Takao Nishizeki (eds.)3540529217, 9783540529217

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. This symposium is the first international symposium organized by SIGAL. In response to the call for papers, 88 papers were submitted from around the world. The program committee selected 34 for presentation at the symposium. The symposium also included 5 invited lectures and 10 invited presentations. The subjects of the papers range widely in the field of discrete algorithms in theoretical computer science. Keywords for these subjects are: computational geometry, graph algorithms, complexity theory, parallel algorithms, distributed computing, and computational algebra.

---

Table of contents :
Recent progress in string algorithms….Pages 1-1
Selection networks….Pages 2-11
Computing edge-connectivity in multiple and capacitated graphs….Pages 12-20
Efficient sequential and parallel algorithms for planar minimum cost flow….Pages 21-30
Structural analyses on the complexity of inverting functions….Pages 31-38
Oracles versus proof techniques that do not relativize….Pages 39-52
20-Relative neighborhood graphs are Hamiltonian….Pages 53-65
The K-Gabriel graphs and their applications….Pages 66-75
Parallel algorithms for generating subsets and set partitions….Pages 76-85
Parallel algorithms for linked list and beyond….Pages 86-100
Local tournaments and proper circular arc graphs….Pages 101-108
Fast algorithms for the dominating set problem on permutation graphs….Pages 109-117
Two probabilistic results on merging….Pages 118-127
Randomized broadcast in networks….Pages 128-137
On the construction of abstract voronoi diagrams, II….Pages 138-154
Searching in higher dimension….Pages 155-155
Finding extrema with unary predicates….Pages 156-164
Implicitly searching convolutions and computing depth of collision….Pages 165-180
Characterization for a family of infinitely many irreducible Equally Spaced Polynomials….Pages 181-190
Distributed algorithms for deciphering….Pages 191-200
An efficient algorithm for optimal loop parallelization (extended abstract)….Pages 201-210
Another view on the SSS* algorithm….Pages 211-220
Algorithms from complexity theory: Polynomial-time operations for complex sets….Pages 221-231
Complexity cores and hard problem instances….Pages 232-240
Spatial point location and its applications….Pages 241-250
Sublinear merging and natural merge sort….Pages 251-260
Constructing strongly convex approximate hulls with inaccurate primitives….Pages 261-270
Computing puiseux-series solutions to determinatal equations via combinatorial relaxation….Pages 271-280
A tight lower bound on the size of planar permutation networks….Pages 281-287
Simultaneous solution of families of problems….Pages 288-299
Algorithms for projecting points to give the most uniform distribution with applications to hashing….Pages 300-309
Topological sweeping in three dimensions….Pages 310-317
Finding least-weight subsequences with fewer processors….Pages 318-327
Derandomization by exploiting redundancy and mutual independence….Pages 328-337
Planar separators and the Euclidean norm….Pages 338-347
On the complexity of isometric embedding in the hypercube….Pages 348-357
Distributed function evaluation in the presence of transmission faults….Pages 358-367
Optimal linear broadcast….Pages 368-377
Graph augmentation problems for a specified set of vertices….Pages 378-387
A heuristic algorithm for the k -center problem with vertex weight….Pages 388-396
Parallel convexity algorithms for digitized images on a linear array of processors….Pages 397-406
Parallel algorithms for labeling image components….Pages 407-418
A hyperplane Incidence problem with applications to counting distances….Pages 419-428
Splitting a configuration in a simplex….Pages 429-438
Weaving patterns of lines and line segments in space….Pages 439-446
Efficient parallel algorithms for path problems in planar directed graphs….Pages 447-457
Parallel algorithms for finding Steiner forests in planar graphs….Pages 458-467
Optimally managing the history of an evolving forest….Pages 468-478