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 |
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 |