3. ISAAC 1992: Nagoya, Japan

Session 1: Invited Papers

• Uzi Vishkin:
  Methods in Parallel Algorithmics and Who May Need to Know Them? 1-5
  
• D. T. Lee:
  Rectilinear Paths among Rectilinear Obstacles. 5-20
  

Session 2A: Graph Algorithms I

• Maw-Hwa Chen, Sing-Ling Lee:
  Linear Time Algorithms for k-cutwidth Problem. 21-30
  
• Toshimasa Watanabe, Toshiya Mashima, Satoshi Taoka:
  The k-Edge-Connectivity Augmentation Problem of Weighted Graphs. 31-40
  
• Sachin B. Patkar, H. Narayanan:
  Principal Lattice of Partition of submodular functions on Graphs: Fast algorithms for Principal Partition and Generic Rigidity. 41-50
  
• R. Z. Hwang, Richard C. T. Lee:
  The Application of the Searching over Separators Strategy to Solve Some NP-Complete Problems on Planar Graphs. 51-60
  

Session 2B: On-Line Algorithms

• Magnús M. Halldórsson:
  Parallel and On-line Graph Coloring Algorithms. 61-70
  
• Tsuyoshi Matsumoto:
  Competitive Analysis of the Round Robin Algorithm. 71-77
  
• Been-Chian Chien, Rong-Jaye Chen, Wei-Pang Yang:
  Competitive Analysis of the On-line Algorithms for Multiple Stacks Sysytems. 78-87
  
• Tony W. Lau:
  Self-Adjusting Augmented Search Trees. 88-96
  

Session 3A: Graph Algorithms II

• Teofilo F. Gonzalez, Toshio Murayama:
  Alhorithms for a Class of Min-Cut and Max-Cut Problem. 97-105
  
• Jan-Ming Ho, Ming-Tat Ko, Tze-Heng Ma, Ting-Yi Sung:
  Algorithms for Rectilinear Optimal Multicast Tree Problem. 106-115
  
• Ton Kloks, Hans L. Bodlaender:
  Approximating Treewidth and Pathwidth of some Classes of Perfect Graphs. 116-125
  
• Shuichi Ueno, Michihiro Yamazaki:
  Graph Spanners and Connectivity. 126-134
  

Session 3B: Parallel Algorithms

• Omer Berkman, Yossi Matias, Uzi Vishkin:
  Randomized Range-Maxima inNearly-Constant Parallel Time. 135-144
  
• Yijie Han, Yoshihide Igarashi, Kumiko Kanai, Kinya Miura:
  Fault-Tolerant Broadcasting in Binary Jumping Networks. 145-154
  
• Kazuo Iwama, Eiji Miyano:
  Routing Problems on the Mesh of Buses. 155-164
  
• Shuji Jimbo, Akira Maruoka:
  Selection Networks with 8n log₂n Size and O(log n) Depth. 165-174
  

Session 4: Invited Papers

• Ronald V. Book:
  Relativizations of the P =?NP and other Problems: Some Developments in Structural Complexity Theory. 175-186
  
• Mike Paterson:
  Boolean Circuit Complexity. 187
  

Session 5A: Computational Geometry I

• Antonios Symvonis, Spyros Tragoudas:
  Searching a Solid Pseudo 3-Sided Orthoconvex Grid. 188-197
  
• Nick D. Dendris, Iannis A. Kalafatis, Lefteris M. Kirousis:
  An Efficient Parallel Algorithm for Geometrically Characterising Drawings of a Class of 3-D Objects. 198-208
  
• Kokichi Sugihara:
  Topologically Consistent Algorithms Realted to Convex Polyhedra. 209-218
  
• Seung-Hak Choi, Sung Yong Shin, Kyung-Yong Chwa:
  Characterizing and Recognizing Visibility Graphs of Funnel-Shaped Polygons. 219-228
  

Session 5B: Complexity Theory I

• Toshiya Itoh, Kenji Horikawa:
  On the Complexity of Composite Numbers. 229-238
  
• Kojiro Kobayashi:
  On Malign Input Distributions for Algorithms. 239-248
  
• Vikraman Arvind, Johannes Köbler, Martin Mundhenk:
  Lowness and the Complexity of Sparse and Tally Descriptions. 249-258
  
• Jie Wang, Jay Belanger:
  Honest Iteration Schemes of Randomizing Algorithms. 259-268
  

Session 6A: Computational Geometry II

• H. S. Lee, R. C. Chang:
  Approximating Vertices of a Convex Polygon with Grid Points in the Polygon. 269-278
  
• Tatsuya Akutsu:
  Algorithms for Determining the Geometrical Congruity in Two and Three Dimensions. 279-288
  
• Esther Jennings, Andrzej Lingas:
  On the Relationship among Constrained Geometric Structures. 289-298
  

Computational Theory

• Klaus Madlener, Friedrich Otto, Andrea Sattler-Klein:
  Generating Small Convergent Systems Can Be Extremely Hard. 299-308
  
• Mizuhito Ogawa:
  Chew's Theorem Revisited -Uniquely Normalizing Property of Nonlinear Term Rewriting Systems-. 309-318
  
• Dominique Bolignano, Mourad Debbabi:
  Higher Order Communication Processes with Value-Passing, Assignment and Return of Results. 319-331
  
• Wim Pijls, Arie de Bruin:
  Searching Informed Game Trees. 332-341
  

Session 7: Invited Papers

• Masao Iri:
  How to Generate Realistic Sample Problems for Network Optimization. 342-350
  
• Silvano Martello, Paolo Toth:
  Generalized Assignment Problems. 351-369
  

Session 8A: Geometry and Layout

• Eric Guévremont, Jack Snoeyink:
  Recognizing an Envelope of Lines in Linear Time. 370-377
  
• W. S. Chan, F. Chin:
  Approximation of Polygonal Curves with Minimum Number of Line Segments. 378-387
  
• Majid Sarrafzadeh, Dorothea Wagner, Frank Wagner, Karsten Weihe:
  Wiring Knock-Knee Layouts: A Global Appoach. 388-399
  
• Jun-ya Takahashi, Hitoshi Suzuki, Takao Nishizeki:
  Algorithms for Finding Non-Crossing Paths with Minimum Total Length in Plane Graphs. 400-409
  

Session 8B: Complexity Theory II

• Luc Longpré, Osamu Watanabe:
  On Symmetry of Information and Polynomial Time Invertibility. 410-419
  
• Richard Beigel, Jun Tarui, Seinosuke Toda:
  On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. 420-429
  
• Kaoru Kurosawa, Osamu Watanabe:
  Computational and Statistical Indistinguishabilities. 430-438
  
• Bin Fu, Hong-Zhou Li:
  On Symmetric Differences of NP-hard Sets with Weakly-P-Selective Sets. 439-448
  

Session 9A: Combinatorial Algorithms

• Majid Sarrafzadeh, D. T. Lee:
  Rstricted Track Assignment with Applications. 449-458
  
• Wen-Lian Hsu:
  A Simple Test for the Consecutive Ones Property. 459-468
  
• Koji Hakata, Hiroshi Imai:
  The Longest Common Subsequence Problem for Small Alphabet Size Between Many Strings. 469-478
  

Session 9B: Data Structures

• Tak Wah Lam, Ka Hing Lee:
  The Implicit Dictionary Problem Revisited. 479-488
  
• Klaus Reinhardt:
  Sorting In-Place with a Worst Case Complexity of n log n-1.3n + O(logn) Comparisons and epsilon n log n + O(1) Transports. 489-498
  
• Alistair Moffat, Ola Petersson, Nicholas C. Wormald:
  Sorting and/by Merging Finger Trees. 499-508