Skip to main content
SpringerLink
Log in

Algorithms and Computation

14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings

  • Conference proceedings
  • © 2003

Overview

Editors:
  1. Toshihide Ibaraki

    1. School of Science and Technology, Kwansei Gakuin University, Sanda, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Naoki Katoh

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Hirotaka Ono

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 2906)

Included in the following conference series:

Conference proceedings info: ISAAC 2003.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (75 papers)

  1. Front Matter

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

  7. 3A Quantum Computation

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

      • V. Arvind, Rainer Schuler
      Pages 168-177
Back to top

Other volumes

  1. Algorithms and Computation

Keywords

About this book

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.

Editors and Affiliations

  • 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

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation