ISA '91 Algorithms

1. Front Matter

   PDF

2. Decision-making with incomplete information

   • Christos H. Papadimitriou

   Pages 1-1

3. Maximum independet set of a permutation graph in k tracks

   • D. T. Lee, Majid Sarrafzadeh

   Pages 2-11

4. Algorithms for square roots of graphs

   • Yaw-Ling Lin, Steven S. Skiena

   Pages 12-21

5. Distributed k-mutual exclusion problem and k-coteries

   • Satoshi Fujita, Masafumi Yamashita, Tadashi Ae

   Pages 22-31

6. Is the shuffle-exchange better than the butterfly?

   • Arvind Raghunathan, Huzur Saran

   Pages 32-41

7. Weighted random assignments with application to hashing

   • Andrew Chi-Chih Yao

   Pages 42-42

8. Scheduling file transfers under port and channel constraints

   • Shin-ichi Nakano, Takao Nishizeki

   Pages 43-51

9. Substitution decomposition on chordal graphs and applications

   • Wen-Lian Hsu, Tze-Heng Ma

   Pages 52-60

10. Mixed-searching and proper-path-width

    • Atsushi Takahashi, Shuichi Ueno, Yoji Kajitani

    Pages 61-71

11. Short wire routing in convex grids

    • Frank Wagner, Barbara Wolfers

    Pages 72-82

12. A new approach to knock-knee channel routing

    • Dorothea Wagner

    Pages 83-93

13. Circuit partitioning algorithms: Graph model versus geometry model

    • Tetsuo Asano, Takeshi Tokuyama

    Pages 94-103

14. Identifying 2-monotonic positive boolean functions in polynomial time

    • E. Boros, P. L. Hammer, T. Ibaraki, K. Kawakami

    Pages 104-115

15. An average case analysis of Monien and Speckenmeyer's mechanical theorem proving algorithm

    • T. H. Hu, C. Y. Tang, R. C. T. Lee

    Pages 116-126

16. An on-line algorithm for navigating in unknown terrain

    • Kwong-fai Chan, Tak Wah Lam

    Pages 127-136

17. On maintaining the width and diameter of a planar point-set online

    • Ravi Janardan

    Pages 137-149

18. Optimal triangulations by retriangulating

    • Herbert Edelsbrunner

    Pages 150-150

19. Approximating polygons and subdivisions with minimum link paths

    • Leonidas J. Guibas, John E. Hershberger, Joseph S. B. Mitchell, Jack Scott Snoeyink

    Pages 151-162

20. An incremental algorithm for constructing shortest watchman routes

    • Xue-Hou Tan, Tomio Hirata, Yasuyoshi Inagaki

    Pages 163-175

This volume presents the proceedings of the Second Annual International Symposium on Algorithms held at Academia Sinica, Taipei, Republic of China, December 16-18, 1991. The symposium was organized by the Institute of Information Science, Academia Sinica, and the National Tsing Hua University. In response to the program committee's call for papers, 90 papers were submitted, from which the committee selected 36 for presentation at the symposium. In addition to these contributed papers, the symposium included 5 invited talks. The subjects of the papers range widely in the area of discrete algorithms, over such topics as computational geometry, graph algorithms, complexity theory, parallel algorithms, distributed computing and computational algebra.

• Complexity Theory
• Computational Geometry
• Distributed Computing
• Graph Algorithms
• Graph-Algorithmen
• Komplexitätstheorie
• Matchings
• Parallel Algorithms
• Parallele Algorithmen
• Partition
• Verteiltes Rechnen
• algorithms
• complexity
• geometry
• statistics
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics