Algorithms and Computation: 9th International Symposium, Isaac'98, Taejon, Korea, December 14-16, 1998, Proceedings

ISBN-13: 9783540653851 / Angielski / Miękka / 1998 / 486 str.

Kyung-Yong Chwa; Oscar H. Ibarra; J. Bosch

Opis

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.

Spis treści

Invited Presentation.- The Discrepancy Method.- Implementing Algorithms and Data Structures: An Educational and Research Perspective.- Geometry I.- L? Voronoi Diagrams and Applications to VLSI Layout and Manufacturing.- Facility Location on Terrains.- Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles.- Complexity I.- Maximizing Agreement with a Classification by Bounded or Unbounded number of Associated Words.- Disjunctions of Horn Theories and Their Cores.- Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently While Concealing It.- Graph Drawing.- Two-Layer Planarization in Graph Drawing.- Computing Orthogonal Drawings in a Variable Embedding Setting.- Dynamic Grid Embedding with Few Bends and Changes.- On-Line Algorithm and Scheduling.- Two New Families of List Update Algorithms.- An Optimal Algorithm for On-Line Palletizing at Delivery Industry.- On-Line Scheduling of Parallel Jobs with Runtime Restrictions.- CAD/CAM and Graphics.- Testing the Quality of Manufactured Disks and Cylinders.- Casting with Skewed Ejection Direction.- Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image.- Graph Algorithm I.- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph.- Polyhedral Structure of Submodular and Posi-modular Systems.- Maximizing the number of Connections in Optical Tree Networks.- Best Paper Presentation.- Selecting the k Largest Elements with Parity Tests.- Randomized Algorithm.- Randomized K-Dimensional Binary Search Trees.- Randomized O(log log n)-Round Leader Election Protocols in Packet Radio Networks.- Random Regular Graphs with Edge Faults: Expansion through Cores.- Complexity II.- A Quantum Polynomial Time Algorithm in Worst Case for Simon’s Problem.- Generalized Graph Colorability and Compressibility of Boolean Formulae.- On the Complexity of Free Monoid Morphisms.- Graph Algorithm II.- Characterization of Efficiently Solvable Problems on Distance-Hereditary Graphs.- Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs.- Finding Planar Geometric Automorphisms in Planar Graphs.- Combinatorial Problem.- New Approach for Speeding Up Enumeration Algorithms.- Hamiltonian Decomposition of Recursive Circulants.- Convertibility among Grid Filling Curves.- Geometry II.- Generalized Self-Approaching Curves.- The Steiner Tree Problem in ?4-geometry Plane.- Computational Biology.- Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-Free Languages.- On the Multiple Gene Duplication Problem.- Geometry III.- Visibility Queries in Simple Polygons and Applications.- Quadtree Decomposition, Steiner Triangulation, and Ray Shooting.- Optimality and Integer Programming Formulations of Triangulations in General Dimension.- Approximation Algorithm.- Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs.- A Capacitated Vehicle Routing Problem on a Tree.- Approximation Algorithms for Some Optimum Communication Spanning Tree Problems.- Complexity III.- The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees.- Inapproximability Results for Guarding Polygons without Holes.- The Inapproximability of Non NP-hard Optimization Problems.- Parallel and Distributed Algorithm.- An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate.- A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution.- Optimal Approximate Agreement with Omission Faults.