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

Sue Whitesides (auth.), Peter Eades, Tadao Takaoka (eds.)3540429859, 9783540429852

This book constitutes the refereed proceedings of the 12th International Conference on Algorithms and Computation, ISAAC 2001, held in Christchurch, New Zealand in December 2001.
The 62 revised full papers presented together with three invited papers were carefully reviewed and selected from a total of 124 submissions. The papers are organized in topical sections on combinatorial generation and optimization, parallel and distributed algorithms, graph drawing and algorithms, computational geometry, computational complexity and cryptology, automata and formal languages, computational biology and string matching, and algorithms and data structures.

---

Table of contents :
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