2. ISA 1991: Taipei, Taiwan

Session 1: Invited Presentation

• Christos H. Papadimitriou:
  Decision-Making with Incomplete Information. 1
  

Session 2A

• D. T. Lee, Majid Sarrafzadeh:
  Maximum Independent Set of a Permutation Graph in k Tracks. 2-11
  
• Yaw-Ling Lin, Steven Skiena:
  Algorithms for Square Roots of Graphs. 12-21
  

Session 2B

• Satoshi Fujita, Masafumi Yamashita, Tadashi Ae:
  Distributed k-Mutual Exclusion Problem and k-Coteries. 22-31
  
• Arvind Raghunathan, Huzur Saran:
  Is the Shuffle-Exchange Better Than the Butterfly? 32-41
  

Session 3: Invited Presentation

• Andrew Chi-Chih Yao:
  Weighted Random Assignments with Application to Hashing. 42
  

Session 4A

• Shin-Ichi Nakano, Takao Nishizeki:
  Scheduling File Transfers under Port and Channel Constraints. 43-51
  
• Wen-Lian Hsu, Tze-Heng Ma:
  Substitution Decomposition on Chordal Graphs and Applications. 52-60
  
• Atsushi Takahashi, Shuichi Ueno, Yoji Kajitani:
  Mixed-Searching and Proper-Path-Width. 61-71
  

Session 4B

• Frank Wagner, Barbara Wolfers:
  Short Wire Routing in Convex Grids. 72-82
  
• Dorothea Wagner:
  A New Approach to Knock-Knee Channel Routing. 83-93
  
• Tetsuo Asano, Takeshi Tokuyama:
  Circuit Partitioning Algorithms: Graph Model versus Geometry Model. 94-103
  

Session 5A

• Endre Boros, Peter L. Hammer, Toshihide Ibaraki, Kazuhiko Kawakami:
  Identifying 2-Monotonic Positive Boolean Functions in Polynominal Time. 104-115
  
• T. H. Hu, Chuan Yi Tang, Richard C. T. Lee:
  An Average Case Analysis of Monien and Speckenmeyer's Mechanical Theorem Proving Algorithm. 116-126
  

Session 5B

• Kwong-fai Chan, Tak Wah Lam:
  An On-Line Algorithm for Navigating in Unknown Terrain. 127-136
  
• Ravi Janardan:
  On Maintaining the Width and Diameter of a Planar Point-Set Online. 137-149
  

Session 6: Invited Presentation

• Herbert Edelsbrunner:
  Optimal Triangulations by Retriangulating. 150
  

Session 7A

• Leonidas J. Guibas, John Hershberger, Joseph S. B. Mitchell, Jack Snoeyink:
  Approximating Polygons and Subdivisions with Minimum Link Paths. 151-162
  
• Xuehou Tan, Tomio Hirata, Yasuyoshi Inagaki:
  An Incremental Algorithm for Constructing Shortest Watchman Routes. 163-175
  
• H. S. Lee, Ruei-Chuan Chang:
  On Hitting Grid Points in a Convex Polygon with Straight Lines. 176-189
  

Session 7B

• A. Benkouar, Yannis Manoussakis, Vangelis Th. Paschos, Rachid Saad:
  On the Complexity of Some Hamiltonian and Eulerian Problems in Edge-Colored Complete Graphs. 190-198
  
• Takao Asano:
  Dynamic Programming on Intervals. 199-207
  
• Wojciech Szpankowski:
  Combinatorial Optimization Through Order Statistics. 208-217
  

Session 8: Invited Presentation

• Leonidas J. Guibas:
  Combinatorics and Algorithms of Geometric Arrangements. 218
  

Session 9A

• Susumu Hasegawa, Hiroshi Imai, Koji Hakata:
  An Analysis of Randomized Shear Sort on the Mesh Computer. 219-228
  
• I-Chen Wu:
  Efficient Parallel Divide-and-Conquer for a Class of Interconnection Topologies. 229-240
  
• Mee Yee Chan, Francis Y. L. Chin, Chung Keung Poon:
  Optimal Specified Root Embedding of Full Binary Trees in Faulty Hypercubes. 241-250
  

Session 9B

• Rudolf Fleischer:
  A Tight Lower Bound for the Worst Case of Bottom-Up Heapsort. 251-262
  
• Alistair Moffat, Ola Petersson:
  Historical Searching and Sorting. 263-272
  
• Arne Andersson, Tony W. Lai:
  Comparison-Efficient And Write-Optimal Searching and Sorting. 273-282
  

Session 10: Invited Presentation

• F. Frances Yao:
  Nearest Neighbors Revisited. 283
  

Session 11 A

• Vladimir Estivill-Castro, Murray Sherk:
  Competitiveness and Response Time in On-Line Algorithms. 284-293
  
• Jan-Ming Ho:
  A Linear Time Optimal Via Assignment Algorithm for Three-Dimensional Channel Routing. 294-307
  
• Luc Longpré, Sarah Mocas:
  Symmetry of Information and One-Way Functions. 308-315
  

Session 11 B

• Lih-Hsing Hsu, Jeng-Yan Hwang, Tung-Yang Ho, Chang-Hsiung Tsai:
  A Linear Time Algorithm to Recognize the Double Euler Trail for Series-Parallel Networks. 316-325
  
• Tsan-sheng Hsu, Vijaya Ramachandran:
  On Finding a Smallest Augmentation to Biconnect a Graph. 326-335
  
• Michael Kaufmann, Gerhard Klär:
  A Faster Algorithm for Edge-Disjoint Paths in Planar Graphs. 336-348
  

Session 12 A

• Hans-Peter Lenhof, Michiel H. M. Smid:
  An Optimal Construction Method for Generalized Convex Layers. 349-363
  
• Michiel H. M. Smid:
  Rectangular Point Location and the Dynamic Closest Pair Problem. 364-374
  

Session 12 B

• Ip-Wang Chan, Donald K. Friesen:
  Parallel Algorithms for Some Dominance Problems Based on a CREW PRAM. 375-384
  
• Krzysztof Diks, Oscar Garrido, Andrzej Lingas:
  Parallel Algorithms for Finding Maximal k-Dependent Sets and Maximal f-Matchings. 385-395
  

Last update Thu May 23 01:52:05 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page