Algorithms and Computation

1. Front Matter

   PDF

2. Invited Talk

   1. Interactive Proofs for Quantum Computation

      • Andrew Chi-Chih Yao

      Pages 1-1

   2. Drawing Plane Graphs

      • Takao Nishizeki

      Pages 2-5

3. 1A Computational Geometry I

   1. Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curve

      • Jinhee Chun, Kunihiko Sadakane, Takeshi Tokuyama

      Pages 6-15

   2. A Dynamic Dictionary for Priced Information with Application

      • Anil Maheshwari, Michiel Smid

      Pages 16-25

   3. Voronoi Diagram in the Flow Field

      • Tetsushi Nishida, Kokichi Sugihara

      Pages 26-35

   4. Polygonal Path Approximation: A Query Based Approach

      • Ovidiu Daescu, Ningfang Mi

      Pages 36-46

4. 1B Graph and Combinatorial Algorithms I

   1. A Vertex Incremental Approach for Dynamically Maintaining Chordal Graphs

      • Anne Berry, Pinar Heggernes, Yngve Villanger

      Pages 47-57

   2. Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees

      • Atsuko Yamaguchi, Hiroshi Mamitsuka

      Pages 58-67

   3. Hotlink Enhancement Algorithms for Web Directories

      • Ori Gerstel, Shay Kutten, Rachel Matichin, David Peleg

      Pages 68-77

   4. Finding a Length-Constrained Maximum-Density Path in a Tree

      • Rung-Ren Lin, Wen-Hsiung Kuo, Kun-Mao Chao

      Pages 78-87

5. 2A Computational Complexity I

   1. The Intractability of Computing the Hamming Distance

      • Bodo Manthey, Rüdiger Reischuk

      Pages 88-97

   2. Infinitely-Often Autoreducible Sets

      • Richard Beigel, Lance Fortnow, Frank Stephan

      Pages 98-107

   3. Limiting Negations in Bounded-Depth Circuits: An Extension of Markov’s Theorem

      • Shao Chin Sung, Keisuke Tanaka

      Pages 108-116

   4. Computational Complexity Measures of Multipartite Quantum Entanglement

      • Tomoyuki Yamakami

      Pages 117-128

6. 2B Graph and Combinatorial Algorithms II

   1. A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs

      • Gabriel Valiente

      Pages 129-137

   2. Polynomial Time 2-Approximation Algorithms for the Minmax Subtree Cover Problem

      • Hiroshi Nagamochi, Kohei Okada

      Pages 138-147

   3. Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

      • Jianer Chen, Iyad A. Kanj, Ge Xia

      Pages 148-157

   4. A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem

      • Hiroaki Yamamoto

      Pages 158-167

7. 3A Quantum Computation

   1. The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems

      • V. Arvind, Rainer Schuler

      Pages 168-177

This volume contains the proceedings of the 14th Annual International S- posium on Algorithms and Computation (ISAAC 2003), held in Kyoto, Japan, 15–17 December 2003. In the past, it was held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), Chennai (1999), Taipei (2000), Christchurch (2001), and Vancouver (2002). ISAACisanannualinternationalsymposiumthatcoverstheverywiderange of topics in algorithms and computation. The main purpose of the symposium is to provide a forum for researchers working in algorithms and the theory of computation where they can exchange ideas in this active research community. In response to our call for papers, we received unexpectedly many subm- sions, 207 papers. The task of selecting the papers in this volume was done by our program committee and referees. After a thorough review process, the committee selected 73 papers. The selection was done on the basis of originality and relevance to the ?eld of algorithms and computation. We hope all accepted papers will eventally appear in scienti?c journals in more polished forms. The best paper award was given for “On the Geometric Dilation of Finite Point Sets” to Annette Ebbers-Baumann, Ansgar Grune ¨ and Rolf Klein. Two eminent invited speakers, Prof. Andrew Chi-Chih Yao of Princeton University and Prof. Takao Nishizeki of Tohoku University, contributed to this proceedings.

• AAC
• algorithms
• combinatorial optimization
• complexity
• computational geometry
• data structures
• game theory
• optimization
• scheduling
• algorithm analysis and problem complexity

• School of Science and Technology, Kwansei Gakuin University, Sanda, Japan

  Toshihide Ibaraki

• Department of Architecture and Architectural Engineering, Kyoto University, Nishikyo-ku, Japan

  Naoki Katoh

• Department of Computer Science and Communication Engineering, Kyushu University, Fukuoka, Japan

  Hirotaka Ono

Policies and ethics