Algorithms and Computation: 9th International Symposium, ISAAC’98 Taejon, Korea, December 14–16, 1998 Proceedings

Bernard Chazelle (auth.), Kyung-Yong Chwa, Oscar H. Ibarra (eds.)3540653856, 9783540653851

This book constitutes the refereed proceedings of the 9th International Symposium on Algorithms and Computation, ISAAC’98, held in Taejon, Korea, in December 1998.
The 47 revised full papers presented were carefully reviewed and selected from a total of 102 submissions. The book is divided in topical sections on computational geometry, complexity, graph drawing, online algorithms and scheduling, CAD/CAM and graphics, graph algorithms, randomized algorithms, combinatorial problems, computational biology, approximation algorithms, and parallel and distributed algorithms.

---

Table of contents :
The Discrepancy Method….Pages 1-3
Implementing Algorithms and Data Structures: An Educational and Research Perspective….Pages 4-8
L∞ Voronoi Diagrams and Applications to VLSI Layout and Manufacturing….Pages 9-19
Facility Location on Terrains….Pages 20-29
Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles….Pages 30-40
Maximizing Agreement with a Classification by Bounded or Unbounded number of Associated Words….Pages 41-49
Disjunctions of Horn Theories and Their Cores….Pages 50-60
Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently While Concealing It….Pages 60-71
Two-Layer Planarization in Graph Drawing….Pages 72-79
Computing Orthogonal Drawings in a Variable Embedding Setting….Pages 80-89
Dynamic Grid Embedding with Few Bends and Changes….Pages 90-99
Two New Families of List Update Algorithms….Pages 100-109
An Optimal Algorithm for On-Line Palletizing at Delivery Industry….Pages 110-118
On-Line Scheduling of Parallel Jobs with Runtime Restrictions….Pages 119-129
Testing the Quality of Manufactured Disks and Cylinders….Pages 130-138
Casting with Skewed Ejection Direction….Pages 139-150
Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image….Pages 151-158
k -Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph….Pages 159-169
Polyhedral Structure of Submodular and Posi-modular Systems….Pages 170-178
Maximizing the number of Connections in Optical Tree Networks….Pages 179-189
Selecting the k Largest Elements with Parity Tests….Pages 190-197
Randomized K -Dimensional Binary Search Trees….Pages 198-209
Randomized O(log log n )-Round Leader Election Protocols in Packet Radio Networks….Pages 210-219
Random Regular Graphs with Edge Faults: Expansion through Cores….Pages 220-229
A Quantum Polynomial Time Algorithm in Worst Case for Simon’s Problem….Pages 230-236
Generalized Graph Colorability and Compressibility of Boolean Formulae….Pages 237-246
On the Complexity of Free Monoid Morphisms….Pages 247-255
Characterization of Efficiently Solvable Problems on Distance-Hereditary Graphs….Pages 257-266
Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs….Pages 267-275
Finding Planar Geometric Automorphisms in Planar Graphs….Pages 277-286
New Approach for Speeding Up Enumeration Algorithms….Pages 287-296
Hamiltonian Decomposition of Recursive Circulants….Pages 297-306
Convertibility among Grid Filling Curves….Pages 307-316
Generalized Self-Approaching Curves….Pages 317-327
The Steiner Tree Problem in λ 4 -geometry Plane….Pages 328-337
Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-Free Languages….Pages 338-347
On the Multiple Gene Duplication Problem….Pages 348-357
Visibility Queries in Simple Polygons and Applications….Pages 358-367
Quadtree Decomposition, Steiner Triangulation, and Ray Shooting….Pages 368-377
Optimality and Integer Programming Formulations of Triangulations in General Dimension….Pages 378-387
Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs….Pages 388-398
A Capacitated Vehicle Routing Problem on a Tree….Pages 399-407
Approximation Algorithms for Some Optimum Communication Spanning Tree Problems….Pages 408-416
The Edge-Disjoint Paths Problem is NP-Complete for Partial k -Trees….Pages 417-426
Inapproximability Results for Guarding Polygons without Holes….Pages 427-437
The Inapproximability of Non NP-hard Optimization Problems….Pages 438-446
An Efficient NC Algorithm for a Sparse k -Edge-Connectivity Certificate….Pages 447-457
A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution….Pages 458-467
Optimal Approximate Agreement with Omission Faults….Pages 468-475