Algorithms and Computation

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 PriorityQueues.- Lower Bounds on Correction Networks.- Approximate Regular Expression Searching with Arbitrary Integer Weights.- Constructing Compressed Suffix Arrays with Large Alphabets.- 4A Computational Geometry II.- On the Geometric Dilation of Finite Point Sets.- On Computing All Immobilizing Grasps of a Simple Polygon with Few Contacts.- Optimal Point Set Projections onto Regular Grids.- 4B Combinatorial Optimization I.- An Approximation Algorithm for Dissecting a Rectangle into Rectangles with Specified Areas.- A Faster Algorithm for Two-Variable Integer Programming.- Efficient Algorithms for Generation of Combinatorial Covering Suites.- 5A Scheduling.- A Better Approximation for the Two-Machine Flowshop Scheduling Problem with Time Lags.- On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates.- Online Scheduling of Parallel Jobs with Dependencies on 2-Dimensional Meshes.- 5B Computational Biology.- Efficient Algorithms for Descendent Subtrees Comparison of Phylogenetic Trees with Applications to Co-evolutionary Classifications in Bacterial Genome.- Settling the Intractability of Multiple Alignment.- Efficient Algorithms for Optimizing Whole Genome Alignment with Noise.- 6A Computational Geometry III.- Segmenting Doughnut-Shaped Objects in Medical Images.- On the Locality Properties of Space-Filling Curves.- Geometric Restrictions on Producible Polygonal Protein Chains.- Symmetric Layout of Disconnected Graphs.- 6B Graph and Combinatorial Algorithms IV.- Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching.- Enumerating Global Roundings of an Outerplanar Graph.- Augmenting Forests to Meet Odd Diameter Requirements.- On the Existence and Determination of Satisfactory Partitions in a Graph.- 7A Distributed and Parallel Algorithms.- A Turn Function Scheme Realized in the Asynchronous Single-Writer/Multi-reader Shared Memory Model.- An Optimal Parallel Algorithm for c-Vertex-Ranking of Trees.- 7B Graph and Combinatorial Algorithms V.- The Student-Project Allocation Problem.- Algorithms for Enumerating Circuits in Matroids.- A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model.- 8A Data Structure.- Succinct Data Structures for Searchable Partial Sums.- Range Mode and Range Median Queries on Lists and Trees.- Quasi-Perfect Minimally Adaptive q-ary Search with Unreliable Tests.- New Ways to Construct Binary Search Trees.- 8B Graph and Combinatorial Algorithms VI.- Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth.- Biconnectivity on Symbolically Represented Graphs: A Linear Solution.- A Dynamic Data Structure for Maintaining Disjoint Paths Information in Digraphs.- Deterministic Algorithm for the t-Threshold Set Problem.- 9A Combinatorial and Network Optimization.- Energy-Efficient Wireless Network Design.- Wavelength Conversion in Shortest-Path All-Optical Networks.- A Heuristic for the Stacker Crane Problem on Trees Which Is Almost Surely Exact.- Flexible Train Rostering.- 9B Computational Complexity and Cryptography.- Counting Complexity Classes over the Reals I: The Additive Case.- Some Properties of One-Pebble Turing Machines with Sublogarithmic Space.- Hypergraph Decomposition and Secret Sharing.- A Promising Key Agreement Protocol.- 10A Game Theory and Randomized Algorithm.- Rapid Mixing of Several Markov Chains for a Hard-Core Model.- Polynomial Time Approximate Sampler for Discretized Dirichlet Distribution.- Fair Cost Allocations under Conflicts - A Game-Theoretic Point ofView -.- Equilibria for Networks with Malicious Users.- 10B Algebraic and Arithmetic Computation.- Quasi-optimal Arithmetic for Quaternion Polynomials.- Upper Bounds on the Complexity of Some Galois Theory Problems.- Unfolded Modular Multiplication.- Gauss Period, Sparse Polynomial, Redundant Basis, and Efficient Exponentiation for a Class of Finite Fields with Small Characteristic.