附註:Includes bibliographical references and index.
Invited Talk -- Interactive Proofs for Quantum Computation -- Drawing Plane Graphs -- 1A Computational Geometry I -- Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curve -- A Dynamic Dictionary for Priced Information with Application -- Voronoi Diagram in the Flow Field -- Polygonal Path Approximation: A Query Based Approach -- 1B Graph and Combinatorial Algorithms I -- A Vertex Incremental Approach for Dynamically Maintaining Chordal Graphs -- Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees -- Hotlink Enhancement Algorithms for Web Directories -- Finding a Length-Constrained Maximum-Density Path in a Tree -- 2A Computational Complexity I -- The Intractability of Computing the Hamming Distance -- Infinitely-Often Autoreducible Sets -- Limiting Negations in Bounded-Depth Circuits: An Extension of Markov's Theorem -- Computational Complexity Measures of Multipartite Quantum Entanglement -- 2B Graph and Combinatorial Algorithms II -- A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs -- Polynomial Time 2-Approximation Algorithms for the Minmax Subtree Cover Problem -- Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems -- A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem -- 3A Quantum Computation -- The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems -- Non-interactive Quantum Perfect and Statistical Zero-Knowledge -- Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur? -- A Faster Lattice Reduction Method Using Quantum Search -- 3B Graph and Combinatorial Algorithms III -- Three Sorting Algorithms Using Priority Queues -- Lower Bounds on Correction Networks -- Approximate Regular Expression Searching with Arbitrary Integer Weights -- Constructing Compressed Suffix Arrays with Large
摘要:This book constitutes the refereed proceedings of the 14th International Symposium on Algorithms and Computation, ISAAC 2003, held in Kyoto, Japan, in December 2003. The 73 revised full papers presented were carefully reviewed and selected from 207 submissions. The papers are organized in topical sections on computational geometry, graph and combinatorial algorithms, computational complexity, quantum computing, combinatorial optimization, scheduling, computational biology, distributed and parallel algorithms, data structures, combinatorial and network optimization, computational complexity and cryptography, game theory and randomized algorithms, and algebraic and arithmetic computation.
