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

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