Algorithms and Computation: 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. Proceedings

Andrew Chi-Chih Yao (auth.), Toshihide Ibaraki, Naoki Katoh, Hirotaka Ono (eds.)3540206957, 9783540206958, 9783540245872

This volume contains the proceedings of the 14th Annual International S- posium on Algorithms and Computation (ISAAC 2003), held in Kyoto, Japan, 15–17 December 2003. In the past, it was held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), Chennai (1999), Taipei (2000), Christchurch (2001), and Vancouver (2002). ISAACisanannualinternationalsymposiumthatcoverstheverywiderange of topics in algorithms and computation. The main purpose of the symposium is to provide a forum for researchers working in algorithms and the theory of computation where they can exchange ideas in this active research community. In response to our call for papers, we received unexpectedly many subm- sions, 207 papers. The task of selecting the papers in this volume was done by our program committee and referees. After a thorough review process, the committee selected 73 papers. The selection was done on the basis of originality and relevance to the ?eld of algorithms and computation. We hope all accepted papers will eventally appear in scienti?c journals in more polished forms. The best paper award was given for “On the Geometric Dilation of Finite Point Sets” to Annette Ebbers-Baumann, Ansgar Grune ¨ and Rolf Klein. Two eminent invited speakers, Prof. Andrew Chi-Chih Yao of Princeton University and Prof. Takao Nishizeki of Tohoku University, contributed to this proceedings.

---

Table of contents :
Front Matter….Pages –
Interactive Proofs for Quantum Computation….Pages 1-1
Drawing Plane Graphs….Pages 2-5
Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curve….Pages 6-15
A Dynamic Dictionary for Priced Information with Application….Pages 16-25
Voronoi Diagram in the Flow Field….Pages 26-35
Polygonal Path Approximation: A Query Based Approach….Pages 36-46
A Vertex Incremental Approach for Dynamically Maintaining Chordal Graphs….Pages 47-57
Finding the Maximum Common Subgraph of a Partial k -Tree and a Graph with a Polynomially Bounded Number of Spanning Trees….Pages 58-67
Hotlink Enhancement Algorithms for Web Directories….Pages 68-77
Finding a Length-Constrained Maximum-Density Path in a Tree….Pages 78-87
The Intractability of Computing the Hamming Distance….Pages 88-97
Infinitely-Often Autoreducible Sets….Pages 98-107
Limiting Negations in Bounded-Depth Circuits: An Extension of Markov’s Theorem….Pages 108-116
Computational Complexity Measures of Multipartite Quantum Entanglement….Pages 117-128
A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs….Pages 129-137
Polynomial Time 2-Approximation Algorithms for the Minmax Subtree Cover Problem….Pages 138-147
Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems….Pages 148-157
A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem….Pages 158-167
The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems….Pages 168-177
Non-interactive Quantum Perfect and Statistical Zero-Knowledge….Pages 178-188
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?….Pages 189-198
A Faster Lattice Reduction Method Using Quantum Search….Pages 199-208
Three Sorting Algorithms Using Priority Queues….Pages 209-220
Lower Bounds on Correction Networks….Pages 221-229
Approximate Regular Expression Searching with Arbitrary Integer Weights….Pages 230-239
Constructing Compressed Suffix Arrays with Large Alphabets….Pages 240-249
On the Geometric Dilation of Finite Point Sets….Pages 250-259
On Computing All Immobilizing Grasps of a Simple Polygon with Few Contacts….Pages 260-269
Optimal Point Set Projections onto Regular Grids….Pages 270-279
An Approximation Algorithm for Dissecting a Rectangle into Rectangles with Specified Areas….Pages 280-289
A Faster Algorithm for Two-Variable Integer Programming….Pages 290-299
Efficient Algorithms for Generation of Combinatorial Covering Suites….Pages 300-308
A Better Approximation for the Two-Machine Flowshop Scheduling Problem with Time Lags….Pages 309-318
On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates….Pages 319-328
Online Scheduling of Parallel Jobs with Dependencies on 2-Dimensional Meshes….Pages 329-338
Efficient Algorithms for Descendent Subtrees Comparison of Phylogenetic Trees with Applications to Co-evolutionary Classifications in Bacterial Genome….Pages 339-351
Settling the Intractability of Multiple Alignment….Pages 352-363
Efficient Algorithms for Optimizing Whole Genome Alignment with Noise….Pages 364-374
Segmenting Doughnut-Shaped Objects in Medical Images….Pages 375-384
On the Locality Properties of Space-Filling Curves….Pages 385-394
Geometric Restrictions on Producible Polygonal Protein Chains….Pages 395-404
Symmetric Layout of Disconnected Graphs….Pages 405-414
Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching….Pages 415-424
Enumerating Global Roundings of an Outerplanar Graph….Pages 425-433
Augmenting Forests to Meet Odd Diameter Requirements….Pages 434-443
On the Existence and Determination of Satisfactory Partitions in a Graph….Pages 444-453
A Turn Function Scheme Realized in the Asynchronous Single-Writer/Multi-reader Shared Memory Model….Pages 454-463
An Optimal Parallel Algorithm for c -Vertex-Ranking of Trees….Pages 464-473
The Student-Project Allocation Problem….Pages 474-484
Algorithms for Enumerating Circuits in Matroids….Pages 485-494
A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model….Pages 495-504
Succinct Data Structures for Searchable Partial Sums….Pages 505-516
Range Mode and Range Median Queries on Lists and Trees….Pages 517-526
Quasi-Perfect Minimally Adaptive q-ary Search with Unreliable Tests….Pages 527-536
New Ways to Construct Binary Search Trees….Pages 537-543
Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth….Pages 544-553
Biconnectivity on Symbolically Represented Graphs: A Linear Solution….Pages 554-564
A Dynamic Data Structure for Maintaining Disjoint Paths Information in Digraphs….Pages 565-574
Deterministic Algorithm for the t -Threshold Set Problem….Pages 575-584
Energy-Efficient Wireless Network Design….Pages 585-594
Wavelength Conversion in Shortest-Path All-Optical Networks….Pages 595-604
A Heuristic for the Stacker Crane Problem on Trees Which Is Almost Surely Exact….Pages 605-614
Flexible Train Rostering….Pages 615-624
Counting Complexity Classes over the Reals I: The Additive Case….Pages 625-634
Some Properties of One-Pebble Turing Machines with Sublogarithmic Space….Pages 635-644
Hypergraph Decomposition and Secret Sharing….Pages 645-654
A Promising Key Agreement Protocol….Pages 655-662
Rapid Mixing of Several Markov Chains for a Hard-Core Model….Pages 663-675
Polynomial Time Approximate Sampler for Discretized Dirichlet Distribution….Pages 676-685
Fair Cost Allocations under Conflicts — A Game-Theoretic Point of View —….Pages 686-695
Equilibria for Networks with Malicious Users….Pages 696-704
Quasi-optimal Arithmetic for Quaternion Polynomials….Pages 705-715
Upper Bounds on the Complexity of Some Galois Theory Problems….Pages 716-725
Unfolded Modular Multiplication….Pages 726-735
Gauss Period, Sparse Polynomial, Redundant Basis, and Efficient Exponentiation for a Class of Finite Fields with Small Characteristic….Pages 736-745
Back Matter….Pages –