9. ISAAC 1998: Taejon, Korea

Kyung-Yong Chwa, Oscar H. Ibarra (Eds.): Algorithms and Computation, 9th International Symposium, ISAAC '98, Taejon, Korea, December 14-16, 1998, Proceedings. Lecture Notes in Computer Science 1533 Springer 1998, ISBN 3-540-65385-6 BibTeX

@proceedings{DBLP:conf/isaac/1998,
  editor    = {Kyung-Yong Chwa and
               Oscar H. Ibarra},
  title     = {Algorithms and Computation, 9th International Symposium, ISAAC
               '98, Taejon, Korea, December 14-16, 1998, Proceedings},
  booktitle = {ISAAC},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1533},
  year      = {1998},
  isbn      = {3-540-65385-6},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Presentation

Bernard Chazelle:
The Discrepancy Method. 1-3
Electronic Edition (Springer LINK) BibTeX
Roberto Tamassia:
Implementing Algorithms and Data Structures: An Educational and Research Perspective. 4-8
Electronic Edition (Springer LINK) BibTeX

Geometry I

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

Complexity I

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

Graph Drawing

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

On-Line Algorithm and Scheduling

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

CAD or CAM and Graphics

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

Graph Algorithm I

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

Best Paper Presentation

Tak Wah Lam, Hing-Fung Ting:
Selecting the k Largest Elements with Parity Tests. 189-198
Electronic Edition (Springer LINK) BibTeX

Randomized Algorithm

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

Complexity II

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

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
Electronic Edition (Springer LINK) BibTeX
Yaw-Ling Lin:
Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs. 267-276
Electronic Edition (Springer LINK) BibTeX
Seok-Hee Hong, Peter Eades, Sang Ho Lee:
Finding Planar Geometric Automorphisms in Planar Graphs. 277-286
Electronic Edition (Springer LINK) BibTeX

Combinatorial Problem

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

Geometry II

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

Computational Biology

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

Geometry III

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

Approximation Algorithm

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

Complexity III

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

Parallel and Distributed Algorithm

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