Algorithms

1. Front Matter

   PDF

2. Recent progress in string algorithms

   • Zvi Galil

   Pages 1-1

3. Selection networks

   • Nicholas Pippenger

   Pages 2-11

4. Computing edge-connectivity in multiple and capacitated graphs

   • Hiroshi Nagamochi, Toshihide Ibaraki

   Pages 12-20

5. Efficient sequential and parallel algorithms for planar minimum cost flow

   • Hiroshi Imai, Kazuo Iwano

   Pages 21-30

6. Structural analyses on the complexity of inverting functions

   • Osamu Watanabe, Seinosuke Toda

   Pages 31-38

7. Oracles versus proof techniques that do not relativize

   • Eric Allender

   Pages 39-52

8. 20-Relative neighborhood graphs are Hamiltonian

   • Maw Shang Chang, C. Y. Tang, R. C. T. Lee

   Pages 53-65

9. The K-Gabriel graphs and their applications

   • Tung-Hsin Su, Ruei-Chuan Chang

   Pages 66-75

10. Parallel algorithms for generating subsets and set partitions

    • Borivoje Djokić, Masahiro Miyakawa, Satoshi Sekiguchi, Ichiro Semba, Ivan Stojmenović

    Pages 76-85

11. Parallel algorithms for linked list and beyond

    • Yijie Han

    Pages 86-100

12. Local tournaments and proper circular arc graphs

    • Pavol Hell, Jørgen Bang-Jensen, Jing Huang

    Pages 101-108

13. Fast algorithms for the dominating set problem on permutation graphs

    • Kuo-Hui Tsai, Wen-Lian Hsu

    Pages 109-117

14. Two probabilistic results on merging

    • Wenceslas Fernandez de la Vega, Sampath Kannan, Miklos Santha

    Pages 118-127

15. Randomized broadcast in networks

    • Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal

    Pages 128-137

16. On the construction of abstract voronoi diagrams, II

    • R. Klein, K. Mehlhorn, S. Meiser

    Pages 138-154

17. Searching in higher dimension

    • Bernard Chazelle

    Pages 155-155

18. Finding extrema with unary predicates

    • David G. Kirkpatrick, Feng Gao

    Pages 156-164

19. Implicitly searching convolutions and computing depth of collision

    • David Dobkin, John Hershberger, David Kirkpatrick, Subhash Suri

    Pages 165-180

20. Characterization for a family of infinitely many irreducible Equally Spaced Polynomials

    • Toshiya Itoh

    Pages 181-190

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.

• algorithm
• algorithms
• complexity
• complexity theory
• computational geometry
• computer
• computer science
• distributed computing
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics