[ISAAC'98] Accepted Papers

[ISAAC '98]

Below is a list of paper accepted to ISAAC'98 to be held in Taejon, Korea
on December 14-16, 1998. More information can be obtained from
the conference web site: http://tclab.kaist.ac.kr/~isaac98/

***************************************************************************

On-Line Scheduling of Parallel Jobs with Runtime Restrictions
--- Stefan Bischof and Ernst W. Mayr

Approximation algorithms for some optimum communication spanning tree problems
--- Bang Ye Wu, Kun-Mao Chao, and Chuan Yi Tang

Approximation and Exact Algorithms for {RNA} Secondary Structure Prediction and Recognition of Stochastic Context-free Languages
--- Tatsuya Akutsu

An optimal algorithm for on-line palletizing at delivery industry
--- J. Rethmann and E. Wanke

Generalized Self-Approaching Curves
--- Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, and Guenter Rote

A New Approach for Speeding Up Enumeration Algorithms
--- Takeaki Uno

Two New Families of List Update Algorithms
--- Frank Schulz

Two-Layer Planarization in Graph Drawing
--- Petra Mutzel and Ren'e Weiskircher

Randomized $O( log log n)$-Round Leader Election Protocols in Packet Radio Networks
--- Koji Nakano and Stephan Olariu

Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image
--- Tetsuo Asano, Hiro Ito, Souichi Kimura, and Nariaki Shimazu

Convertibility among Grid Filling Curves
--- Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama

Selecting the k Largest Elements with Parity Tests
--- T.W. Lam and H.F. Ting

Disjunctions of Horn Theories and their Cores
--- Thomas Eiter, Toshihide Ibaraki, and Kazuhisa Makino

Optimality and Integer Programming Formulations of Triangulations in General Dimension
--- Akira Tajima

Computing Orthogonal Drawings in a Variable Embedding Setting
--- W. Didimo and G. Liotta

Inapproximability results for guarding polygons without holes
--- Stephan Eidenbenz

Polyhedral Structure in Submodular and Posi-modular Systems
--- Hiroshi Nagamochi and Toshihide Ibaraki

The Edge-Disjoint Paths Problem is NP-Complete for Partial $k$-Trees
--- Xiao Zhou and Takao Nishizeki

Checking Programs Discretely: Demonstrating Result-Correctness Efficiently While Concealing It
--- G.D. Crescenzo, K. Sakurai, , and M. Yung

Dynamic Grid Embedding with Few Bends and Changes
--- Ulrik Brandes and Dorothea Wagner

Maximizing the Number of Connections in Optical Tree Networks
--- Thomas Erlebach and Klaus Jansen

A parallel algorithm for sampling matchings from an almost uniform distribution
--- J. Diaz, J. Petit, P. Psycharis, and M. Serna

Randomized $k$-Dimensional Binary Search Trees
--- Amalia Duch, Vladimir Estivill-Castro, and Conrado Martinez

On the inapproximability of non NP-hard optimization problems
--- Liming Cai, David Juedes, , and Iyad Kanj

Quadtree Decomposition, Steiner Triangulation, and Ray shooting
--- Siu-Wing Cheng and Kam-Hing Lee

Casting with Skewed Ejection Direction
--- Hee kap Ahn, Siu-Wing Cheng, and Otfried Cheong

An Efficient NC Algorithm for a Sparse $k$-Edge-Connectivity Certificate
--- Hiroshi Nagamochi and Toru Hasunuma

Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs
--- Yaw-Ling Lin

Space-efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs
--- Philip N. Klein and Hsueh-I Lu

On the Multiple Gene Duplication Problem
--- Michael Fellows, Michael Hallett, and Ulrike Stege

$L_\infty$ Voronoi Diagrams and Applications to VLSI Layout and Manufacturing
--- Evanthia Papadopoulou

Characterization of Efficiently Computable Problems on Distance-Hereditary Graphs
--- Sun yuan Hsieh, Chin wen Ho, Tsan sheng Hsu, Ming tat Ko, and Gen-Huey Chen

An Algorithm for Finding Geometric Automorphisms in Planar Graphs
--- Seok-Hee Hong, Peter Eades, and Sang-Ho Lee

Facility Location on Terrains
--- Boris Aronov, Marc van Kreveld, Ren'e van Oostrum, and Kasturirangan Varadarajan

A Quantum Polynomial Time Algorithm in Worst Case for Simon's Problem
--- Takashi Mihara and Shao-Chin Sung

Optimal Approximate Agreement with Omission Faults
--- Richard Plunkett and Alan Fekete

$k$-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
--- Toshimasa Ishii, Hiroshi Nagamochi, and Toshihide Ibaraki

The Steiner tree problem in $\lambda_4$-geometry plane
--- Guo-Hui Lin and Guoliang Xue

Generalized Graph Colorability and Compressibility of Boolean Formulae
--- Richard Nock, Pascal Jappy, and Jean Sallantin

A Capacitated Vehicle Routing Problem on a Tree
--- Shin ya Hamaguchi and Naoki Katoh

Visibility Queries in Simple Polygons and Applications
--- Boris Aronov, Leonidas J. Guibas, Marek Teichmann, and Li Zhang

Hamiltonian decomposition of recursive circulants
--- Jung-Heum Park

On the Complexity of Free Monoid Morphisms
--- Klaus-Joern Lange and Pierre McKenzie

Testing the quality of manufactured disks and cylinders
--- Prosenjit Bose and Pat Morin

Random Regular Graphs with Edge Faults Expansion through Cores
--- Andreas Goerdt

Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles
--- Joonsoo Choi, Chan-Su Shin, and Sung Kwon Kim

Maximizing Agreement with a Classification by Bounded or Unbounded Number of Words
--- Hiroki Arimura and Shinichi Shimozono


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme