+612 9045 4394
Algorithms and Computation : 9th International Symposium, Isaac'98, Taejon, Korea, December 14-16, 1998, Proceedings - Kyung-Yong Chwa

Algorithms and Computation

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

By: Kyung-Yong Chwa (Editor), Oscar H. Ibarra (Editor)


Published: 23rd November 1998
Ships: 15 business days
15 business days
or 4 easy payments of $39.60 with Learn more

The papers in this volume were selected for presentation at the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98), heldonDecember14-16,1998inTaejon, Korea.P- viousmeetingswereheldinTokyo(1990), Taipei(1991), Nagoya (1992), HongKong(1993), Beijing(1994), Cairns(1995), Osaka (1996), andSingapore(1997). The symposium was jointly sponsored by Korea Advanced - stitute of Science and Technology (KAIST) and Korea Information Science Society (KISS) to commemorate its 25th anniversary in - operationwithMinistryofInformationandCommunication, Korea InformationSocietyDevelopmentInstitute, andKoreaScienceand Engineering Foundation. Inresponsetothecallforpapers,102extendedabstractswere submitted from 21 countries. Each submitted paper was reported on byatleastfourprogramcommitteemembers, withtheassistance ofreferees, asindicatedbytherefereelistfoundintheseproce- ings. There were many more acceptable papers than there was space availableinthesymposiumschedule, andtheprogramcommittee's task was extremely di?cult. The 47 papers selected for presentation hadatotalof105authors, residentasfollows: Japan24, Germany 17, UnitedStateofAmerica15, Taiwan10, HongKongandKorea 6each, Spain5, SwitzerlandandAustralia4each, Austria, Canada, andFrance3each, ItalyandNetherlands2each, andGreece1. We thank all program committee members and their referees fortheirexcellentwork, especiallygiventhedemandingtimec- straints; they gave the symposium its distinctive character. We thank all who submitted papers for consideration: they all contributed to the high quality of the symposium. Finally, wethankallthepeoplewhoworkedhardtoputinplace the logistical arrangements of the symposium - our colleagues and our graduate students. It is their hard work that made the sym- sium possible and enjoyable.

Invited Presentation
The Discrepancy Methodp. 1
Implementing Algorithms and Data Structures: An Educational and Research Perspectivep. 4
Geometry I
L Voronoi Diagrams and Applications to VLSI Layout and Manufacturingp. 9
Facility Location on Terrainsp. 19
Computing Weighted Rectilinear Median and Center Set in the Presence of Obstaclesp. 29
Complexity I
Maximizing Agreement with a Classification by Bounded or Unbounded Number of Associated Wordsp. 39
Disjunctions of Horn Theories and Their Coresp. 49
Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently While Concealing Itp. 59
Graph Drawing
Two-Layer Planarization in Graph Drawingp. 69
Computing Orthogonal Drawings in a Variable Embedding Settingp. 79
Dynamic Grid Embedding with Few Bends and Changesp. 89
On-Line Algorithm and Scheduling
Two New Families of List Update Algorithmsp. 99
An Optimal Algorithm for On-Line Palletizing at Delivery Industryp. 109
On-Line Scheduling of Parallel Jobs with Runtime Restrictionsp. 119
CAD/CAM and Graphics
Testing the Quality of Manufactured Disks and Cylindersp. 129
Casting with Skewed Ejection Directionp. 139
Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Imagep. 149
Graph Algorithm I
k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraphp. 159
Polyhedral Structure of Submodular and Posi-modular Systemsp. 169
Maximizing the Number of Connections in Optical Tree Networksp. 179
Best Paper Presentation
Selecting the k Largest Elements with Parity Testsp. 189
Randomized Algorithm
Randomized K-Dimensional Binary Search Treesp. 199
Randomized 0(log log n)-Round Leader Election Protocols in Packet Radio Networksp. 209
Random Regular Graphs with Edge Faults: Expansion through Coresp. 219
Complexity II
A Quantum Polynomial Time Algorithm in Worst Case for Simon's Problemp. 229
Generalized Graph Colorability and Compressibility of Boolean Formulaep. 237
On the Complexity of Free Monoid Morphismsp. 247
Graph Algorithm II
Characterization of Efficiently Solvable Problems on Distance-Hereditary Graphsp. 257
Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphsp. 267
Finding Planar Geometric Automorphisms in Planar Graphsp. 277
Combinatorial Problem
A New Approach for Speeding Up Enumeration Algorithmsp. 287
Hamiltonian Decomposition of Recursive Circulantsp. 297
Convertibility among Grid Filling Curvesp. 307
Geometry II
Generalized Self-Approaching Curvesp. 317
The Steiner Tree Problem in 4-geometry Planep. 327
Computational Biology
Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-Free Languagesp. 337
On the Multiple Gene Duplication Problemp. 347
Geometry III
Visibility Queries in Simple Polygons and Applicationsp. 357
Quadtree Decomposition and Steiner Triangulation and Ray Shootingp. 367
Optimality and Integer Programming Formulations of Triangulations in General Dimensionp. 377
Approximation Algorithm
Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programsp. 387
A Capacitated Vehicle Routing Problem on a Treep. 397
Approximation Algorithms for Some Optimum Communication Spanning Tree Problemsp. 407
Complexity III
The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Treesp. 417
Inapproximability Results for Guarding Polygons without Holesp. 427
The Inapproximability of Non NP-hard Optimization Problemsp. 437
Parallel and Distributed Algorithm
An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificatep. 447
A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distributionp. 457
Optimal Approximate Agreement with Omission Faultsp. 467
Author Indexp. 477
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9783540653851
ISBN-10: 3540653856
Series: Lecture Notes in Computer Science,
Audience: General
Format: Paperback
Language: English
Number Of Pages: 486
Published: 23rd November 1998
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 2.57
Weight (kg): 0.69