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

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 -