Ebook: Algorithms and Computation: 11th International Conference, ISAAC 2000 Taipei, Taiwan, December 18–20, 2000 Proceedings

The papers in this volume were selected for presentation at the Eleventh Annual International Symposium on Algorithms and Computation (ISAAC 2000), held on 18{20 December, 2000 at the Institute of Information Science, Academia Sinica, Taipei, Taiwan. Previous meetings were held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), and Chennai (1999). Submissions to the conference this year were conducted entirely electro- cally. Thanks to the excellent software developed by the Institute of Information Science, Academia Sinica, we were able to carry out virtually all communication via the World Wide Web. In response to the call for papers, a total of 87 extended abstracts were submitted from 25 countries. Each submitted paper was handled by at least three program committee members, with the assistance of a number of external reviewers, as indicated by the referee list found in the proceedings. There were many more acceptable papers than there was space available in the symposium program, which made the program committee’s task extremely di cult. Finally 46 papers were selected for presentation at the Symposium. In addition to these contributed papers, the conference also included two invited presentations by Dr. Jean-Daniel Boissonnat, INRIA Sophia-Antipolis, France and Professor Jin-Yi Cai, University of Wisconsin at Madison, Wisconsin, USA. It is expected that most of the accepted papers will appear in a more complete form in scienti c journals.

---

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.

---

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.

Content:
Front Matter....Pages I-XIV
Voronoi-Based Systems of Coordinates and Surface Reconstruction....Pages 1-1
Essentially Every Unimodular Matrix Defines an Expander....Pages 2-22
Strategies for Hotlink Assignments....Pages 23-34
A New Competitive Analysis of Randomized Caching....Pages 35-46
Online Routing in Convex Subdivisions....Pages 47-59
A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors....Pages 60-71
Classification of Various Neighborhood Operations for the Nurse Scheduling Problem....Pages 72-83
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets....Pages 84-95
Coping with Delays and Time-Outs in Binary Search Procedures....Pages 96-107
Some Formal Analysis of Rocchio’s Similarity-Based Relevance Feedback Algorithm....Pages 108-119
Reasoning with Ordered Binary Decision Diagrams....Pages 120-131
On Approximating Minimum Vertex Cover for Graphs with Perfect Matching....Pages 132-143
A 2-Approximation Algorithm for Path Coloring on Trees of Rings....Pages 144-155
An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree....Pages 156-167
Finding Independent Spanning Trees in Partial k-Trees....Pages 168-179
On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover....Pages 180-191
Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width....Pages 192-203
Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits....Pages 204-215
A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the Plane....Pages 216-227
Simple Algorithms for a Weighted Interval Selection Problem....Pages 228-240
Efficient Minus and Signed Domination in Graphs....Pages 241-253
Convex Grid Drawings of Four-Connected Plane Graphs....Pages 254-265
An Algorithm for Finding Three Dimensional Symmetry in Series Parallel Digraphs....Pages 266-277
Undecidability Results for Monoids with Linear-Time Decidable Word Problems....Pages 278-289
Secret Key Exchange Using Random Deals of Cards on Hierarchical Structures....Pages 290-301
Derandomizing Arthur-Merlin Games under Uniform Assumptions....Pages 302-312
A Near Optimal Algorithm for Vertex Connectivity Augmentation....Pages 313-325
Simultaneous Augmentation of Two Graphs to an ?Edge-Connected Graph and a Biconnected Graph....Pages 326-337
Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets....Pages 338-349
An Intuitive and Effective New Representation for Interconnection Network Structures....Pages 350-361
Randomized Leader Election Protocols in Radio Networks with no Collision Detection....Pages 362-373
Deterministic Broadcasting Time with Partial Knowledge of the Network....Pages 374-385
Minimizing Makespan in Batch Machine Scheduling....Pages 386-397
Preemptive Parallel Task Scheduling in O(n) + Poly(m) Time....Pages 398-409
Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array....Pages 410-421
A Better Lower Bound for Two-Circle Point Labeling....Pages 422-431
Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a Point Set....Pages 432-443
An Improved Algorithm for Subdivision Traversal without Extra Storage....Pages 444-455
Generalized H-Coloring of Graphs....Pages 456-466
Finding a Two-Core of a Tree in Linear Time....Pages 467-478
Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparison....Pages 479-490
Optimal Beam Penetrations in Two and Three Dimensions....Pages 491-502
Searching a Simple Polygon by a k-Searcher....Pages 503-514
Characterization of Rooms Searchable by Two Guards....Pages 515-526
Improved Phylogeny Comparisons: Non-shared Edges, Nearest Neighbor Interchanges, and Subtree Transfers....Pages 527-538
Phylogenetic k-Root and Steiner k-Root....Pages 539-551
Maintenance of a Piercing Set for Intervals with Applications....Pages 552-563
Optimal Polygon Cover Problems and Applications....Pages 564-576
Back Matter....Pages 577-578

---

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.

Content:
Front Matter....Pages I-XIV
Voronoi-Based Systems of Coordinates and Surface Reconstruction....Pages 1-1
Essentially Every Unimodular Matrix Defines an Expander....Pages 2-22
Strategies for Hotlink Assignments....Pages 23-34
A New Competitive Analysis of Randomized Caching....Pages 35-46
Online Routing in Convex Subdivisions....Pages 47-59
A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors....Pages 60-71
Classification of Various Neighborhood Operations for the Nurse Scheduling Problem....Pages 72-83
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets....Pages 84-95
Coping with Delays and Time-Outs in Binary Search Procedures....Pages 96-107
Some Formal Analysis of Rocchio’s Similarity-Based Relevance Feedback Algorithm....Pages 108-119
Reasoning with Ordered Binary Decision Diagrams....Pages 120-131
On Approximating Minimum Vertex Cover for Graphs with Perfect Matching....Pages 132-143
A 2-Approximation Algorithm for Path Coloring on Trees of Rings....Pages 144-155
An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree....Pages 156-167
Finding Independent Spanning Trees in Partial k-Trees....Pages 168-179
On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover....Pages 180-191
Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width....Pages 192-203
Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits....Pages 204-215
A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the Plane....Pages 216-227
Simple Algorithms for a Weighted Interval Selection Problem....Pages 228-240
Efficient Minus and Signed Domination in Graphs....Pages 241-253
Convex Grid Drawings of Four-Connected Plane Graphs....Pages 254-265
An Algorithm for Finding Three Dimensional Symmetry in Series Parallel Digraphs....Pages 266-277
Undecidability Results for Monoids with Linear-Time Decidable Word Problems....Pages 278-289
Secret Key Exchange Using Random Deals of Cards on Hierarchical Structures....Pages 290-301
Derandomizing Arthur-Merlin Games under Uniform Assumptions....Pages 302-312
A Near Optimal Algorithm for Vertex Connectivity Augmentation....Pages 313-325
Simultaneous Augmentation of Two Graphs to an ?Edge-Connected Graph and a Biconnected Graph....Pages 326-337
Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets....Pages 338-349
An Intuitive and Effective New Representation for Interconnection Network Structures....Pages 350-361
Randomized Leader Election Protocols in Radio Networks with no Collision Detection....Pages 362-373
Deterministic Broadcasting Time with Partial Knowledge of the Network....Pages 374-385
Minimizing Makespan in Batch Machine Scheduling....Pages 386-397
Preemptive Parallel Task Scheduling in O(n) + Poly(m) Time....Pages 398-409
Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array....Pages 410-421
A Better Lower Bound for Two-Circle Point Labeling....Pages 422-431
Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a Point Set....Pages 432-443
An Improved Algorithm for Subdivision Traversal without Extra Storage....Pages 444-455
Generalized H-Coloring of Graphs....Pages 456-466
Finding a Two-Core of a Tree in Linear Time....Pages 467-478
Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparison....Pages 479-490
Optimal Beam Penetrations in Two and Three Dimensions....Pages 491-502
Searching a Simple Polygon by a k-Searcher....Pages 503-514
Characterization of Rooms Searchable by Two Guards....Pages 515-526
Improved Phylogeny Comparisons: Non-shared Edges, Nearest Neighbor Interchanges, and Subtree Transfers....Pages 527-538
Phylogenetic k-Root and Steiner k-Root....Pages 539-551
Maintenance of a Piercing Set for Intervals with Applications....Pages 552-563
Optimal Polygon Cover Problems and Applications....Pages 564-576
Back Matter....Pages 577-578
....