Algorithms and Computation: 12th International Symposium, ISAAC 2001 Christchurch, New Zealand, December 19–21, 2001 Proceedings

Chain Reconfiguration The Ins and Outs, Ups and Downs of Moving Polygons and Polygonal Linkages....Pages 1-13
Application of M-Convex Submodular Flow Problem to Mathematical Economics....Pages 14-25
A Polynomial Time Approximation Scheme for Minimizing Total Completion Time of Unbounded Batch Scheduling....Pages 26-35
A Polynomial Time Approximation Scheme for the Multi-vehicle Scheduling Problem on a Path with Release and Handling Times....Pages 36-48
Semi-normal Schedulings: Improvement on Goemans’ Algorithm....Pages 48-60
Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness....Pages 61-73
Broadcasting with Universal Lists Revisited: Using Competitive Analysis....Pages 74-85
On Adaptive Fault Diagnosis for Multiprocessor Systems....Pages 86-98
On-Line Multicasting in All-Optical Networks....Pages 99-106
Enumerating Floorplans with n Rooms....Pages 107-115
On Min-Max Cycle Bases....Pages 116-123
On the Minimum Local-Vertex-Connectivity Augmentation in Graphs....Pages 124-135
Counting Graph Isomorphisms among Chordal Graphs with Restricted Clique Number....Pages 136-147
Quantum Algorithms for Intersection and Proximity Problems....Pages 148-159
BUSHWHACK: An Approximation Algorithm for Minimal Paths through Pseudo-Euclidean Spaces....Pages 160-171
Approximation of Minimum Triangulation for Polyhedron with Bounded Degrees....Pages 172-184
Tree-Approximations for the Weighted Cost-Distance Problem....Pages 185-195
Necessary and Sufficient Numbers of Cards for Sharing Secret Keys on Hierarchical Groups....Pages 196-207
Generic Algorithms and Key Agreement Protocols Based on Group Actions....Pages 208-218
Baire Category and Nowhere Differentiability for Feasible Real Functions....Pages 219-230
Translation among CNFs, Characteristic Models and Ordered Binary Decision Diagrams....Pages 231-243
On Removing the Pushdown Stack in Reachability Constructions....Pages 244-256
A New Recognition Algorithm for Extended Regular Expressions....Pages 257-267
Polynomial-Time Algorithms for the Equivalence for One-Way Quantum Finite Automata....Pages 268-278
An Index for the Data Size to Extract Decomposable Structures in LAD....Pages 279-290
Parameterized Complexity: The Main Ideas and Some Research Frontiers....Pages 291-307
Tight Bounds on Maximal and Maximum Matchings....Pages 308-319
Recognition and Orientation Algorithms for P4-Comparability Graphs....Pages 320-331
Efficient Algorithms for k -Terminal Cuts on Planar Graphs....Pages 332-344
Polynomial Time Algorithms for Edge-Connectivity Augmentation of Hamiltonian Paths....Pages 345-354
Algorithms for Pattern Involvement in Permutations....Pages 355-367
A Fast Algorithm for Enumerating Bipartite Perfect Matchings....Pages 367-379
On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time....Pages 380-389
On the Complexity of Train Assignment Problems....Pages 390-402
A Combinatorial Toolbox for Protein Sequence Design and Landscape Analysis in the Grand Canonical Model....Pages 403-415
Complexity of Comparing Hidden Markov Models....Pages 416-428
DNA Self-Assembly For Constructing 3D Boxes....Pages 429-441
Exact Solutions for Closest String and Related Problems....Pages 441-453
Topological Peeling and Implementation....Pages 454-466
Image Segmentation with Monotonicity and Smoothness Constraints....Pages 467-479
Optimization Algorithms for Sweeping a Polygonal Region with Mobile Guards....Pages 480-492
Approximation of a Geometric Set Covering Problem....Pages 493-501
Shortest Path Algorithms: Engineering Aspects....Pages 502-513
Efficient Algorithms for Weighted Colorings of Series-Parallel Graphs....Pages 514-524
Go with the Winners Algorithms for Cliques in Random Graphs....Pages 525-537
Complexity of Partial Covers of Graphs....Pages 537-549
On Game-Theoretic Models of Networks....Pages 550-561
The Complexity of Some Basic Problems for Dynamic Process Graphs....Pages 562-574
Delay Optimizations in Quorum Consensus....Pages 575-586
Randomized Shared Queues Applied to Distributed Optimization Algorithms....Pages 587-599
Multiprocess Time Queue....Pages 599-609
Labeling Points with Weights....Pages 610-622
Small Convex Quadrangulations of Point Sets....Pages 623-635
How to Color a Checkerboard with a Given Distribution — Matrix Rounding Achieving Low 2 × 2-Discrepancy....Pages 636-648
Labeling Subway Lines....Pages 649-659
Complexity Study on Two Clustering Problems....Pages 660-669
A Modified Greedy Algorithm for the Set Cover Problem with Weights 1 and 2....Pages 670-681
A Unified Framework for Approximating Multiway Partition Problems....Pages 682-694
On-Line Algorithms for Cardinality Constrained Bin Packing Problems....Pages 695-706
Suffix Vector: A Space-Efficient Suffix Tree Representation....Pages 707-718
Fragmentary Pattern Matching: Complexity, Algorithms and Applications for Analyzing Classic Literary Works....Pages 719-730
Computing the Quartet Distance between Evolutionary Trees in Time O ( n log 2 n )....Pages 731-742
The Cent-dian Path Problem on Tree Networks....Pages 743-755
Approximate Hotlink Assignment....Pages 756-767
Efficient Algorithms for Two Generalized 2-Median Problems on Trees....Pages 768-778