9. ISAAC 1998: Taejon, Korea

Invited Presentation

• Bernard Chazelle:
  The Discrepancy Method. 1-3
  
• Roberto Tamassia:
  Implementing Algorithms and Data Structures: An Educational and Research Perspective. 4-8
  

Geometry I

• Evanthia Papadopoulou:
  L_infinity Voronoi Diagrams and Applications to VLSI Layout and Manufacturing. 9-18
  
• Boris Aronov, Marc J. van Kreveld, René van Oostrum, Kasturi R. Varadarajan:
  Facility Location on Terrains. 19-28
  
• Joonsoo Choi, Chan-Su Shin, Sung Kwon Kim:
  Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles. 29-38
  

Complexity I

• Hiroki Arimura, Shinichi Shimozono:
  Maximizing Agreement with a Classification by Bounded or Unbounded Number of Associated Words. 39-48
  
• Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino:
  Disjunctions of Horn Theories and Their Cores. 49-58
  
• Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung:
  Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently while Concealing it. 59-68
  

Graph Drawing

• Petra Mutzel, René Weiskircher:
  Two-Layer Planarization in Graph Drawing. 69-78
  
• Walter Didimo, Giuseppe Liotta:
  Computing Orthogonal Drawings in a Variable Embedding Setting. 79-88
  
• Ulrik Brandes, Dorothea Wagner:
  Dynamic Grid Embedding with Few Bends and Changes. 89-98
  

On-Line Algorithm and Scheduling

• Frank Schulz:
  Two New Families of List Update Algorithms. 99-108
  
• Jochen Rethmann, Egon Wanke:
  An Optimal Algorithm for On-Line Palletizing at Delivery Industry. 109-118
  
• Stefan Bischof, Ernst W. Mayr:
  On-Line Scheduling of Parallel Jobs with Runtime Restrictions. 119-128
  

CAD or CAM and Graphics

• Prosenjit Bose, Pat Morin:
  Testing the Quality of Manufactured Disks and Cylinders. 129-138
  
• Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong:
  Casting with Skewed Ejection Direction. 139-148
  
• Tetsuo Asano, Hiro Ito, Souichi Kimura, Shigeaki Shimazu:
  Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image. 149-158
  

Graph Algorithm I

• Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki:
  K-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph. 159-168
  
• Hiroshi Nagamochi, Toshihide Ibaraki:
  Polyhedral Structure of Submodular and Posi-modular Systems. 169-178
  
• Thomas Erlebach, Klaus Jansen:
  Maximizing the Number of Connections in Optical Tree Networks. 179-188
  

Best Paper Presentation

• Tak Wah Lam, Hing-Fung Ting:
  Selecting the k Largest Elements with Parity Tests. 189-198
  

Randomized Algorithm

• Amalia Duch, Vladimir Estivill-Castro, Conrado Martínez:
  Randomized K-Dimensional Binary Search Trees. 199-208
  
• Koji Nakano, Stephan Olariu:
  Randomized O (log log n)-Round Leader Election Protocols in Packet Radio Networks. 209-218
  
• Andreas Goerdt:
  Random Regular Graphs with Edge Faults: Expansion through Cores. 219-228
  

Complexity II

• Takashi Mihara, Shao Chin Sung:
  A Quantum Polynomial Time Algorithm in Worst Case for Simon's Problem. 229-236
  
• Richard Nock, Pascal Jappy, Jean Sallantin:
  Generalized Graph Colorability and Compressibility of Boolean Formulae. 237-246
  
• Klaus-Jörn Lange, Pierre McKenzie:
  On the Complexity of Free Monoid Morphisms. 247-256
  

Graph Algorithm II

• Sun-Yuan Hsieh, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, Gen-Huey Chen:
  Characterization of Efficiently Solvable Problems on Distance-Hereditary Graphs. 257-266
  
• Yaw-Ling Lin:
  Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs. 267-276
  
• Seok-Hee Hong, Peter Eades, Sang Ho Lee:
  Finding Planar Geometric Automorphisms in Planar Graphs. 277-286
  

Combinatorial Problem

• Takeaki Uno:
  A New Approach for Speeding Up Enumeration Algorithms. 287-296
  
• Jung-Heum Park:
  Hamiltonian Decomposition of Recursive Circulants. 297-306
  
• Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama:
  Convertibility among Grid Filling Curves. 307-316
  

Geometry II

• Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, Günter Rote:
  Generalized Self-Approaching Curves. 317-326
  
• Guo-Hui Lin, Guoliang Xue:
  The Steiner Tree Problem in Lambda₄-geometry Plane. 327-336
  

Computational Biology

• Tatsuya Akutsu:
  Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-Free Languages. 337-346
  
• Michael R. Fellows, Michael T. Hallett, Ulrike Stege:
  On the Multiple Gene Duplication Problem. 347-356
  

Geometry III

• Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang:
  Visibility Queries in Simple Polygons and Applications. 357-366
  
• Siu-Wing Cheng, Kam-Hing Lee:
  Quadtree Decomposition, Steiner Triangulation, and Ray Shooting. 367-376
  
• Akira Tajima:
  Optimality and Integer Programming Formulations of Triangulations in General Dimension. 377-386
  

Approximation Algorithm

• Philip N. Klein, Hsueh-I Lu:
  Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs. 387-396
  
• Shin-ya Hamaguchi, Naoki Katoh:
  A Capacitated Vehicle Routing Problem on a Tree. 397-406
  
• Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang:
  Approximation Algorithms for Some Optimum Communication Spanning Tree Problems. 407-416
  

Complexity III

• Xiao Zhou, Takao Nishizeki:
  The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees. 417-426
  
• Stephan Eidenbenz:
  Inapproximability Results for Guarding Polygons without Holes. 427-436
  
• Liming Cai, David W. Juedes, Iyad A. Kanj:
  The Inapproximability of Non NP-hard Optimization Problems. 437-446
  

Parallel and Distributed Algorithm

• Hiroshi Nagamochi, Toru Hasunuma:
  An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate. 447-456
  
• Josep Díaz, Jordi Petit, Panagiotis Psycharis, Maria J. Serna:
  A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution. 457-466
  
• Richard Plunkett, Alan Fekete:
  Optimal Approximate Agreement with Omission Faults. 467-475