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

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