Skip to main content
SpringerLink
Log in

Algorithms and Computation

11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000. Proceedings

  • Conference proceedings
  • © 2000

Overview

Editors:
  1. Gerhard Goos

    1. Karlsruhe University, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Juris Hartmanis

    1. Cornell University, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Jan Leeuwen

    1. Utrecht University, The Netherlands

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. D. T. Lee

    1. Academia Sinica, Institute of Information Science, Taipei, Taiwan, R.O.C.

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Shang-Hua Teng

    1. Department of Computer Science and Akamai Technologies, University of Illinois at Urbana Champaign, Cambridge, USA

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

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 (48 papers)

  1. Front Matter

    Pages I-XIV
    Download chapter PDF

  2. Invited Presentations

    1. Voronoi-Based Systems of Coordinates and Surface Reconstruction

      • Jean-Daniel Boissonnat
      Pages 1-1

    2. Essentially Every Unimodular Matrix Defines an Expander

      • Jin-Yi Cai
      Pages 2-22

  3. Algorithms and Data Structures (I)

    1. Strategies for Hotlink Assignments

      • Prosenjit Bose, Jurek Czyzowicz, Leszek Gąsieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc et al.
      Pages 23-34

    2. A New Competitive Analysis of Randomized Caching

      • Ching Law, Charles E. Leiserson
      Pages 35-46

    3. Online Routing in Convex Subdivisions

      • Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Alejandro López-Ortiz et al.
      Pages 47-59

  4. Combinatorial Optimization

    1. A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors

      • Jingui Huang, Jianer Chen, Songqiao Chen
      Pages 60-71

    2. Classification of Various Neighborhood Operations for the Nurse Scheduling Problem

      • Takayuki Osogami, Hiroshi Imai
      Pages 72-83

    3. Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets

      • Yuyu Chen, Ming-Yang Kao, Hsueh-I. Lu
      Pages 84-95

  5. Algorithms and Data Structures (II)

    1. Coping with Delays and Time-Outs in Binary Search Procedures

      • Ferdinando Cicalese, Ugo Vaccaro
      Pages 96-107

    2. Some Formal Analysis of Rocchio’s Similarity-Based Relevance Feedback Algorithm

      • Zhixiang Chen, Binhai Zhu
      Pages 108-119

    3. Reasoning with Ordered Binary Decision Diagrams

      • Takashi Horiyama, Toshihide Ibaraki
      Pages 120-131

  6. Approximation and Randomized Algorithms (I)

    1. On Approximating Minimum Vertex Cover for Graphs with Perfect Matching

      • Jianer Chen, Iyad A. Kanj
      Pages 132-143

    2. A 2-Approximation Algorithm for Path Coloring on Trees of Rings

      • Xiaotie Deng, Guojun Li, Wenan Zang, Yi Zhou
      Pages 144-155

    3. An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree

      • Q. S. Wu, C. L. Lu, R. C. T. Lee
      Pages 156-167

  7. Algorithms and Data Structures (III)

    1. Finding Independent Spanning Trees in Partial k-Trees

      • Xiao Zhou, Takao Nishizeki
      Pages 168-179

    2. On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover

      • Rolf Niedermeier, Peter Rossmanith
      Pages 180-191

    3. Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width

      • Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
      Pages 192-203

  8. Approximation and Randomized Algorithms (II)

    1. Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits

      • Takao Asano, Magnús M. Halldórsson, Kazuo Iwama, Takeshi Matsuda
      Pages 204-215

    2. A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the Plane

      • Norihiro Kubo, Katsuhiro Muramoto, Shinichi Shimozono
      Pages 216-227
Back to top

Keywords

About this book

The papers in this volume were selected for presentation at the Eleventh Annual International Symposium on Algorithms and Computation (ISAAC 2000), held on 18{20 December, 2000 at the Institute of Information Science, Academia Sinica, Taipei, Taiwan. Previous meetings were held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), and Chennai (1999). Submissions to the conference this year were conducted entirely electro- cally. Thanks to the excellent software developed by the Institute of Information Science, Academia Sinica, we were able to carry out virtually all communication via the World Wide Web. In response to the call for papers, a total of 87 extended abstracts were submitted from 25 countries. Each submitted paper was handled by at least three program committee members, with the assistance of a number of external reviewers, as indicated by the referee list found in the proceedings. There were many more acceptable papers than there was space available in the symposium program, which made the program committee’s task extremely di cult. Finally 46 papers were selected for presentation at the Symposium. In addition to these contributed papers, the conference also included two invited presentations by Dr. Jean-Daniel Boissonnat, INRIA Sophia-Antipolis, France and Professor Jin-Yi Cai, University of Wisconsin at Madison, Wisconsin, USA. It is expected that most of the accepted papers will appear in a more complete form in scienti c journals.

Editors and Affiliations

  • Karlsruhe University, Germany

    Gerhard Goos

  • Cornell University, USA

    Juris Hartmanis

  • Utrecht University, The Netherlands

    Jan Leeuwen

  • Academia Sinica, Institute of Information Science, Taipei, Taiwan, R.O.C.

    D. T. Lee

  • Department of Computer Science and Akamai Technologies, University of Illinois at Urbana Champaign, Cambridge, USA

    Shang-Hua Teng

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation