| Invited Talk |
| Interactive Proofs for Quantum Computation Andrew Chi-Chih Yao 1 |
| Drawing Plane Graphs Takao Nishizeki 2 |
| 1A Computational Geometry I |
| Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curve Jinhee Chun, Kunihiko Sadakane, Takeshi Tokuyama 6 |
| A Dynamic Dictionary for Priced Information with Application Anil Maheshwari, Michiel Smid 16 |
| Voronoi Diagram in the Flow Field Tetsushi Nishida, Kokichi Sugihara 26 |
| Polygonal Path Approximation: A Query Based Approach Ovidiu Daescu, Ningfang Mi 36 |
| 1B Graph and Combinatorial Algorithms I |
| A Vertex Incremental Approach for Dynamically Maintaining Chordal Graphs Anne Berry, Pinar Heggernes, Yngve Villanger 47 |
| Finding the Maximum Common Subgraph of a Partial κ-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees Atsuko Yamaguchi, Hiroshi Mamitsuka 58 |
| Hotlink Enhancement Algorithms for Web Directories Ori Gerstel, Shay Kutten, Rachel Matichin, David Peleg 68 |
| Finding a Length-Constrained Maximum-Density Path in a Tree Rung-Ren Lin, Wen-Hsiung Kuo, Kun-Mao Chao 78 |
| 2A Computational Complexity I |
| The Intractability of Computing the Hamming Distance Bodo Manthey, Ruediger Reischuk 88 |
| Infinitely-Often Autoreducible Sets Richard Beigel, Lance Fortnow, Frank Stephan 98 |
| Limiting Negations in Bounded-Depth Circuits: An Extension of Markov's Theorem Shao Chin Sung, Keisuke Tanaka 108 |
| Computational Complexity Measures of Multipartite Quantum Entanglement Tomoyuki Yamakami 117 |
| 2B Graph and Combinatorial Algorithms II |
| A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs Gabriel Valiente 129 |
| Polynomial Time 2-Approximation Algorithms for the Minmax Subtree Cover Probem Hiroshi Nagamochi, Kohei Okada 138 |
| Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems Jianer Chen, Iyad A. Kanj, Ge Xia 148 |
| A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem Hiroaki Yamamoto 158 |
| 3A Quantum Computation |
| The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems V. Arvind, Rainer Schuler 168 |
| Non-interactive Quantum Perfect and Statistical Zero-Knowledge Hirotada Kobayashi 178 |
| Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur? Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami 189 |
| A Faster Lattice Reduction Method Using Quantum Search Christoph Ludwig 199 |
| 3B Graph and Combinatorial Algorithms III |
| Three Sorting Algorithms Using Priority Queues Amr Elmasry 209 |
| Lower Bounds on Correction Networks Grzegorz Stachowiak 221 |
| Approximate Regular Expression Searching with Arbitrary Integer Weights Gonzalo Navarro 230 |
| Constructing Compressed Suffix Arrays with Large Alphabets Wing-Kai Hon, Tak-Wah Lam, Kunihiko Sadakane, Wing-Kin Sung 240 |
| 4A Computational Geometry II |
| On the Geometric Dilation of Finite Point Sets Annette Ebbers-Baumann, Ansgar Gruene, Rolf Klein 250 |
| On Computing All Immobilizing Grasps of a Simple Polygon with Few Contacts Jae-Sook Cheong, Herman J. Haverkort, A. Frank van der Stappen 260 |
| Optimal Point Set Projections onto Regular Grids Jose Miguel Diaz-Banez, Ferran Hurtado, Mario Alberto Lopez, J. Antoni Sellares 270 |
| 4B Combinatorial Optimization I |
| An Approximation Algorithm for Dissecting a Rectangle into Rectangles with Specified Areas Hiroshi Nagamochi, Yuusuke Abe 280 |
| A Faster Algorithm for Two-Variable Integer Programming Friedrich Eisenbrand, Soeren Laue 290 |
| Efficient Algorithms for Generation of Combinatorial Covering Suites Adrian Dumitrescu 300 |
| 5A Scheduling |
| A Better Approximation for the Two-Machine Flowshop Scheduling Problem with Time Lags Yoshiyuki Karuno, Hiroshi Nagamochi 309 |
| On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates Aleksei V. Fishkin, Klaus Jansen, Monaldo Mastrolilli 319 |
| Online Scheduling of Parallel Jobs with Dependencies on 2-Dimensional Meshes Deshi Ye, Guochuan Zhang 329 |
| 5B Computational Biology |
| Efficient Algorithms for Descendent Subtrees Comparison of Phylogenetic Trees with Applications to Co-evolutionary Classifications in Bacterial Genome Yaw-Ling Lin, Tsan-Sheng Hsu 339 |
| Settling the Intractability of Multiple Alignment Isaac Elias 352 |
| Efficient Algorithms for Optimizing Whole Genome Alignment with Noise T.W. Lam, N. Lu, H.F. Ting, Prudence W.H. Wong, S.M. Yiu 364 |
| 6A Computational Geometry III |
| Segmenting Doughnut-Shaped Objects in Medical Images Xiaodong Wu 375 |
| On the Locality Properties of Space-Filling Curves H.K. Dai, H.C. Su 385 |
| Geometric Restrictions on Producible Polygonal Protein Chains Erik D. Demaine, Stefan Langerman, Joseph O'Rourke 395 |
| Symmetric Layout of Disconnected Graphs Seok-Hee Hong, Peter Eades 405 |
| 6B Graph and Combinatorial Algorithms IV |
| Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching Miroslav Chlebik, Janka Chlebikova 415 |
| Enumerating Global Roundings of an Outerplanar Graph Nadia Takki-Chebihi, Takeshi Tokuyama 425 |
| Augmenting Forests to Meet Odd Diameter Requirements Toshimasa Ishii, Shigeyuki Yamamoto, Hiroshi Nagamochi 434 |
| On the Existence and Determination of Satisfactory Partitions in a Graph Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten 444 |
| 7A Distributed and Parallel Algorithms |
| A Turn Function Scheme Realized in the Asynchronous Single-Writer/Multi-reader Shared Memory Model Tom Altman, Yoshihide Igarashi, Michiko Omori 454 |
| An Optimal Parallel Algorithm for c-Vertex-Ranking of Trees Md. Abul Kashem, M. Ziaur Rahman 464 |
| 7B Graph and Combinatorial Algorithms V |
| The Student-Project Allocation Problem David J. Abraham, Robert W. Irving, David F. Manlove 474 |
| Algorithms for Enumerating Circuits in Matroids Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan 485 |
| A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model Akinobu Eguchi, Satoru Fujishige, Akihisa Tamura 495 |
| 8A Data Structure |
| Succinct Data Structures for Searchable Partial Sums Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung 505 |
| Range Mode and Range Median Queries on Lists and Trees Danny Krizanc, Pat Morin, Michiel Smid 517 |
| Quasi-Perfect Minimally Adaptive q-ary Search with Unreliable Tests Ferdinando Cicalese, Christian Deppe 527 |
| New Ways to Construct Binary Search Trees Travis Gagie 537 |
| 8B Graph and Combinatorial Algorithms VI |
| Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth Artur Czumaj, Andrzej Lingas, Johan Nilsson 544 |
| Biconnectivity on Symbolically Represented Graphs: A Linear Solution Raffaella Gentilini, Alberto Policriti 554 |
| A Dynamic Data Structure for Maintaining Disjoint Paths Information in Digraphs Torsten Tholey 565 |
| Deterministic Algorithm for the t-Threshold Set Problem Jeremy Barbay, Claire Kenyon 575 |
| 9A Combinatorial and Network Optimization |
| Energy-Efficient Wireless Network Design Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos 585 |
| Wavelength Conversion in Shortest-Path All-Optical Networks Thomas Erlebach, Stamatis Stefanakos 595 |
| A Heuristic for the Stacker Crane Problem on Trees which Is Almost Surely Exact Amin Coja-Oghlan, Sven O. Krumke, Till Nierhoff 605 |
| Flexible Train Rostering Stephan Eidenbenz, Aris Pagourtzis, Peter Widmayer 615 |
| 9B Computational Complexity and Cryptography |
| Counting Complexity Classes over the Reals I: The Additive Case Peter Buergisser, Felipe Cucker 625 |
| Some Properties of One-Pebble Turing Machines with Sublogarithmic Space Atsuyuki Inoue, Akira Ito, Katsushi Inoue, Tokio Okazaki 635 |
| Hypergraph Decomposition and Secret Sharing Giovanni Di Crescenzo, Clemente Galdi 645 |
| A Promising Key Agreement Protocol Eun-Kyung Ryu, Kee-Won Kim, Kee-Young Yoo 655 |
| 10A Game Theory and Randomized Algorithm |
| Rapid Mixing of Several Markov Chains for a Hard-Core Model Ravi Kannan, Michael W. Mahoney, Ravi Montenegro 663 |
| Polynomial Time Approximate Sampler for Discretized Dirichlet Distribution Tomomi Matsui, Mitsuo Motoki, Naoyuki Kamatani 676 |
| Fair Cost Allocations under Conflicts - A Game-Theoretic Point of View - Yoshio Okamoto 686 |
| Equilibria for Networks with Malicious Users George Karakostas, Anastasios Viglas 696 |
| 10B Algebraic and Arithmetic Computation |
| Quasi-optimal Arithmetic for Quaternion Polynomials Martin Ziegler 705 |
| Upper Bounds on the Complexity of Some Galois Theory Problems V. Arvind, Piyush P Kurur 716 |
| Unfolded Modular Multiplication Wieland Fischer, Jean-Pierre Seifert 726 |
| Gauss Period, Sparse Polynomial, Redundant Basis, and Efficient Exponentiation for a Class of Finite Fields with Small Characteristic Soonhak Kwon, Chang Hoon Kim, Chun Pyo Hong 736 |
| Author Index 747 |
| Invited Talk |
| Interactive Proofs for Quantum Computation Andrew Chi-Chih Yao 1 |
| Drawing Plane Graphs Takao Nishizeki 2 |
