Algorithms and Computation: 11th International Conference, Isaac 2000, Taipei, Taiwan, December 18-20, 2000 : Proceedings

by Lee, D. T.; Teng, Shang-Hua

• ISBN13: 9783540412557
• ISBN10: 3540412557
• eBook ISBN(s): 9783540409960
• Format: Paperback
• Copyright: 2001-01-01
• Publisher: Springer Verlag
• More Book Details
• Purchase Benefits

Summary

This book constitutes the refereed proceedings of the 11th International Conference on Algorithms and Computation, ISAAC 2000, held in Taipei, Taiwan in December 2000.The 46 revised papers presented together with an invited paper were carefully reviewed and selected from 87 submissions. The papers are organized in topical sections on algorithms and data structures; combinatorial optimization; approximation and randomized algorithms; graph drawing and graph algorithms; automata, cryptography, and complexity theory; parallel and distributed algorithms; computational geometry; and computational biology.

Table of Contents

Invited Presentations
Voronoi-Based Systems of Coordinates and Surface Reconstruction	1	(1)
Jean-Daniel Boissonnat
Essentially Every Unimodular Matrix Defines an Expander	2	(21)
Jin-Yi Cai
Algorithms and Data Structures (I)
Strategies for Hotlink Assignments	23	(12)
Prosenjit Bose
Evangelos Kranakis
Danny Krizanc
Miguel Vargas Martin
Jurek Czyzowicz
Andrzej Pelc
Leszek Gasieniec
A New Competitive Analysis of Randomized Caching	35	(12)
Ching Law
Charles E. Leiserson
Online Routing in Convex Subdivisions	47	(13)
Prosenjit Bose
Pat Morin
Andrej Brodnik
Svante Carlsson
Erik D. Demaine
Rudolf Fleischer
J. Ian Munro
Alejandro Lopez-Ortiz
Combinatorial Optimization
A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors	60	(12)
Jingui Huang
Jianer Chen
Songqiao Chen
Classification of Various Neighborhood Operations for the Nurse Scheduling Problem	72	(12)
Takayuki Osogami
Hiroshi Imai
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets	84	(12)
Yuyu Chen
Ming-Yang Kao
Hsueh-I. Lu
Algorithms and Data Structures (II)
Coping with Delays and Time-Outs in Binary Search Procedures	96	(12)
Ferdinando Cicalese
Ugo Vaccaro
Some Formal Analysis of Rocchio's Similarity-Based Relevance Feedback Algorithm	108	(12)
Zhixiang Chen
Binhai Zhu
Reasoning with Ordered Binary Decision Diagrams	120	(12)
Takashi Horiyama
Toshihide Ibaraki
Approximation and Randomized Algorithms (I)
On Approximating Minimum Vertex Cover for Graphs with Perfect Matching	132	(12)
Jianer Chen
Iyad A. Kanj
A 2-Approximation Algorithm for Path Coloring on Trees of Rings	144	(12)
Xiaotie Deng
Yi Zhou
Guojun Li
Wenan Zang
An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree	156	(12)
Q. S. Wu
C. L. Lu
R. C. T. Lee
Algorithms and Data Structures (III)
Finding Independent Spanning Trees in Partial k-Trees	168	(12)
Xiao Zhou
Takao Nishizeki
On Efficient Fixed Parameter Algorithms for WEIGHTED VERTEX COVER	180	(12)
Rolf Niedermeier
Peter Rossmanith
Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width	192	(12)
Dimitros M. Thilikos
Maria J. Serna
Hans L. Bodlaender
Approximation and Randomized Algorithms (II)
Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits	204	(12)
Takao Asano
Magnus M. Halldorsson
Kazuo Iwama
Takeshi Matsuda
A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the Plane	216	(12)
Norihiro Kubo
Shinichi Shimozono
Katsuhiro Muramoto
Simple Algorithms for a Weighted Interval Selection Problem	228	(13)
Thomas Erlebach
Frits C. R. Spieksma
Graph Drawing and Algorithms
Efficient Minus and Signed Domination in Graphs	241	(13)
Chin Lung Lu
Sheng-Lung Peng
Chuan Yi Tang
Convex Grid Drawings of Four-Connected Plane Graphs	254	(12)
Kazuyuki Miura
Takao Nishizeki
Shin-ichi Nakano
An Algorithm for Finding Three Dimensional Symmetry in Series Parallel Digraphs	266	(12)
Seok-Hee Hong
Peter Eades
Automata, Cryptography, and Complexity Theory
Undecidability Results for Monoids with Linear-Time Decidable Word Problems	278	(12)
Masashi Katsura
Yuji Kobayashi
Friedrich Otto
Secret Key Exchange Using Random Deals of Cards on Hierarchical Structures	290	(12)
Reina Yoshikawa
Shimin Guo
Kazuhiro Motegi
Yoshihide Igarashi
Derandomizing Arthur-Merlin Games under Uniform Assumptions	302	(11)
Chi-Jen Lu
Algorithms and Data Structures (IV)
A Near Optimal Algorithm for Vertex Connectivity Augmentation	313	(13)
Bill Jackson
Tibor Jordan
Simultaneous Augmentation of Two Graphs to an l-Edge-Connected Graph and a Biconnected Graph	326	(12)
Toshimasa Ishii
Hiroshi Nagamochi
Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets	338	(12)
Hiro Ito
Yuichiro Itatsu
Hideyuki Uehara
Mitsuo Yokoyama
Motoyasu Ito
Parallel and Distributed Algorithms
An Intuitive and Effective New Representation for Interconnection Network Structures	350	(12)
Jianer Chen
Lihua Liu
Songqiao Chen
Weijia Jia
Randomized Leader Election Protocols in Radio Networks with No Collision Detection	362	(12)
Koji Nakano
Stephan Olariu
Deterministic Broadcasting Time with Partial Knowledge of the Network	374	(12)
Gianluca De Marco
Andrzej Pelc
Algorithms and Data Structures (V)
Minimizing Makespan in Batch Machine Scheduling	386	(12)
Chung Keung Poon
Pixing Zhang
Preemptive Parallel Task Scheduling in O(n) + Poly(m) Time	398	(12)
Klaus Jansen
Lorant Porkolab
Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array	410	(12)
Kunihiko Sadakane
Computational Geometry (I)
A Better Lower Bound for Two-Circle Point Labeling	422	(10)
Alexander Wolff
Michael Thon
Yinfeng Xu
Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a Point Set	432	(12)
Deok-Soo Kim
Donguk Kim
Kokichi Sugihara
An Improved Algorithm for Subdivision Traversal without Extra Storage	444	(12)
Prosenjit Bose
Pat Morin
Algorithms and Data Structures (VI)
Generalized H-Coloring of Graphs	456	(11)
Petter Kristiansen
Jan Arne Telle
Finding a Two-Core of a Tree in Linear Time	467	(12)
Biing-Fing Wang
Jyh-Jye Lin
Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparison	479	(12)
Ming-Yang Kao
Tak-Wah Lam
Wing-Kin Sung
Hing-Fung Ting
Computational Geometry (II)
Optimal Beam Penetrations in Two and Three Dimensions	491	(12)
Danny Z. Chen
Xiaobo S. Hu
Jinhui Xu
Searching a Simple Polygon by a k-Searcher	503	(12)
Xuehou Tan
Characterization of Rooms Searchable by Two Guards	515	(12)
Sang-Min Park
Kyung-Yong Chwa
Jae-Ha Lee
Computational Biology
Improved Phylogeny Comparisons: Non-shared Edges, Nearest Neighbor Interchanges, and Subtree Transfers	527	(12)
Wing-Kai Hon
Tak-Wah Lam
Ming-Yang Kao
Phylogenetic k-Root and Steiner k-Root	539	(13)
Guo-Hui Lin
Tao Jiang
Paul E. Kearney
Computational Geometry (III)
Maintenance of a Piercing Set for Intervals with Applications	552	(12)
Matthew J. Katz
Frank Nielsen
Michael Segal
Optimal Polygon Cover Problems and Applications	564	(13)
Danny Z. Chen
Xiaobo S. Hu
Xiaodong Wu
Author Index	577