Skip to main content
SpringerLink
Log in
Book cover

Computing and Combinatorics

5th Annual International Conference, COCOON'99, Tokyo, Japan, July 26-28, 1999, Proceedings

  • Conference proceedings
  • © 1999

Overview

Editors:
  1. Takano Asano

    1. Department of Information and System Engineering Faculty of Science and Engineering, Chuo University, Tokyo, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Hideki Imai

    1. Department of Information Science, University of Tokyo, Tokyo, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. D. T. Lee

    1. Academia Sinica, Institute of Information Science, Nankang, Taipei, Taiwan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Shin-ichi Nakano

    1. Department of Computer Science Faculty of Engineering, Gunma University, Gunma, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Takeshi Tokuyama

    1. IBM Tokyo Research Laboratory, Yamato Kanagawa, 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 1627)

Included in the following conference series:

Conference proceedings info: COCOON 1999.

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 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.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 Talks

    1. The Web as a Graph: Measurements, Models, and Methods

      • Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew S. Tomkins
      Pages 1-17

    2. Some Observations on the Computational Complexity of Graph Accessibility Problem (Extended Abstract)

      • Jun Tarui, Seinosuke Toda
      Pages 18-30

  3. Hao Wang Award Paper

    1. An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree

      • Hiroshi Nagamochi, Toshihide Ibaraki
      Pages 31-40

  4. Data Structures

    1. Theory of 2-3 Heaps

      • Tadao Takaoka
      Pages 41-50

    2. An External Memory Data Structure for Shortest Path Queries (Extended Abstract)

      • David Hutchinson, Anil Maheshwari, Norbert Zeh
      Pages 51-60

  6. Graph Drawing

    1. An Approximation Algorithm for the Two-Layered Graph Drawing Problem

      • Atsuko Yamaguchi, Akihiro Sugimoto
      Pages 81-91

    2. Area Minimization for Grid Visibility Representation of Hierarchically Planar Graphs

      • Xuemin Lin, Peter Eades
      Pages 92-102

    3. Layout Problems on Lattice Graphs

      • Josep Díaz, Mathew D. Penrose, Jordi Petit, María Serna
      Pages 103-112

  7. Discrete Mathematics

    1. A New Transference Theorem in the Geometry of Numbers

      • Jin-Yi Cai
      Pages 113-122

    2. On Covering and Rank Problems for Boolean Matrices and Their Applications

      • Carsten Damm, Ki Hang Kim, Fred Roush
      Pages 123-133

    3. A Combinatorial Algorithm for Pfaffians

      • Meena Mahajan, P. R. Subramanya, V. Vinay
      Pages 134-143

  8. Graph Algorithms 1

    1. How to Swap a Failing Edge of a Single Source Shortest Paths Tree

      • Enrico Nardelli, Guido Proietti, Peter Widmayer
      Pages 144-153

    2. On Bounds for the k-Partitioning of Graphs

      • S. L. Bezrukov, R. Elsässer, U. -P. Schroeder
      Pages 154-163

    3. A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs

      • Hiroshi Nagamochi, Shigeki Katayama, Toshihide Ibaraki
      Pages 164-173

  9. Automata and Language

    1. Probabilities to Accept Languages by Quantum Finite Automata

      • Andris Ambainis, Richard Bonner, Rūsiņš Freivalds, Arnolds Ķikusts
      Pages 174-183

    2. Distributionally-Hard Languages

      • Lance Fortnow, A. Pavan, Alan L. Selman
      Pages 184-193

    3. Circuits and Context-Free Languages

      • Pierre McKenzie, Klaus Reinhardt, V. Vinay
      Pages 194-203
Back to top

Other volumes

  1. Computing and Combinatorics

Keywords

About this book

The abstracts and papers in this volume were presented at the Fifth Annual International Computing and Combinatorics Conference (COCOON ’99), which was held in Tokyo, Japan from July 26 to 28, 1999. The topics cover most aspects of theoretical computer science and combinatorics pertaining to computing. In response to the call for papers, 88 high-quality extended abstracts were submitted internationally, of which 46 were selected for presentation by the p- gram committee. Every submitted paper was reviewed by at least three program committee members. Many of these papers represent reports on continuing - search, and it is expected that most of them will appear in a more polished and complete form in scienti c journals. In addition to the regular papers, this v- ume contains abstracts of two invited plenary talks by Prabhakar Raghavan and Seinosuke Toda. The conference also included a special talk by Kurt Mehlhorn on LEDA (Library of E cient Data types and Algorithms). The Hao Wang Award (inaugurated at COCOON ’97) is given to honor the paper judged by the program committee to have the greatest scienti c merit. The recipients of the Hao Wang Award 1999 were Hiroshi Nagamochi and Tos- hide Ibaraki for their paper \An Approximation for Finding a Smallest 2-Edge- Connected Subgraph Containing a Speci ed Spanning Tree".

Editors and Affiliations

  • Department of Information and System Engineering Faculty of Science and Engineering, Chuo University, Tokyo, Japan

    Takano Asano

  • Department of Information Science, University of Tokyo, Tokyo, Japan

    Hideki Imai

  • Academia Sinica, Institute of Information Science, Nankang, Taipei, Taiwan

    D. T. Lee

  • Department of Computer Science Faculty of Engineering, Gunma University, Gunma, Japan

    Shin-ichi Nakano

  • IBM Tokyo Research Laboratory, Yamato Kanagawa, Japan

    Takeshi Tokuyama

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation