Skip to main content
SpringerLink
Log in
Book cover

Algorithms and Computation

19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Seok-Hee Hong

    1. School of Information Technologies, University of Sydney, Australia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Hiroshi Nagamochi

    1. Graduate School of Informatics, Kyoto University, Kyoto, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Takuro Fukunaga

    1. Graduate School of Informatics, Kyoto University, 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 5369)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: ISAAC 2008.

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

  1. Front Matter

    Download chapter PDF

  3. 1A Approximation Algorithm I

    1. Greedy Construction of 2-Approximation Minimum Manhattan Network

      • Zeyu Guo, He Sun, Hong Zhu
      Pages 4-15

    2. The Complexity of Minimum Convex Coloring

      • Frank Kammer, Torsten Tholey
      Pages 16-27

    3. On the Complexity of Reconfiguration Problems

      • Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara et al.
      Pages 28-39

    4. Multiobjective Disk Cover Admits a PTAS

      • Christian Glaßer, Christian Reitwießner, Heinz Schmitz
      Pages 40-51

  4. 1B Online Algorithm

    1. Data Stream Algorithms via Expander Graphs

      • Sumit Ganguly
      Pages 52-63

    2. Improving the Competitive Ratio of the Online OVSF Code Assignment Problem

      • Shuichi Miyazaki, Kazuya Okamoto
      Pages 64-76

    3. Optimal Key Tree Structure for Deleting Two or More Leaves

      • Weiwei Wu, Minming Li, Enhong Chen
      Pages 77-88

    4. Comparing First-Fit and Next-Fit for Online Edge Coloring

      • Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, Rodica Mihai
      Pages 89-99

  5. 2A Data Structure and Algorithm

    1. Selecting Sums in Arrays

      • Gerth Stølting Brodal, Allan Grønlund Jørgensen
      Pages 100-111

    2. Succinct and I/O Efficient Data Structures for Traversal in Trees

      • Craig Dillabaugh, Meng He, Anil Maheshwari
      Pages 112-123

    3. Space-Time Tradeoffs for Longest-Common-Prefix Array Computation

      • Simon J. Puglisi, Andrew Turpin
      Pages 124-135

    4. Power Domination in \(\mathcal{O}^*(1.7548^n)\) Using Reference Search Trees

      • Daniel Raible, Henning Fernau
      Pages 136-147

  6. 2B Game Theory

    1. The Isolation Game: A Game of Distances

      • Yingchao Zhao, Wei Chen, Shang-Hua Teng
      Pages 148-158

    2. On a Non-cooperative Model for Wavelength Assignment in Multifiber Optical Networks

      • Evangelos Bampas, Aris Pagourtzis, George Pierrakos, Katerina Potika
      Pages 159-170

    3. The Complexity of Rationalizing Matchings

      • Shankar Kalyanaraman, Christopher Umans
      Pages 171-182

    4. A Game Theoretic Approach for Efficient Graph Coloring

      • Panagiota N. Panagopoulou, Paul G. Spirakis
      Pages 183-195
Back to top

Other volumes

  1. Algorithms and Computation

Keywords

About this book

This volume contains the proceedings of the 19th International Symposium on Algorithmsand Computation (ISAAC 2008),held on the Gold Coast, Australia, December 15–17, 2008. In the past, it was held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Daejeon (1998), Chennai (1999), Taipei (2000), Christchurch (2001), Vancouver (2002), Kyoto (2003), Hong Kong (2004), Hainan (2005), Kolkata (2006), and Sendai (2007). ISAACis anannualinternationalsymposiumthatcoversthe verywide range of topics in the ?eld of algorithms and computation. The main purpose of the symposium is to provide a forum for researchers working in algorithms and theoryofcomputationfrom allovertheworld.In responseto ourcallfor papers, we received 229 submissions from 40 countries. The task of selecting the papers in this volume was done by our Program Committee and many other external reviewers. After an extremely rigorous review process and extensive discussion, the Committee selected 78 papers. We hope all accepted papers will eventually appear in scienti?c journals in a more polished form. Two special issues, one of Algorithmica and one of the International Journal on Computational Geometry and Applications, with selected papers from ISAAC 2008 are in preparation.

Editors and Affiliations

  • School of Information Technologies, University of Sydney, Australia

    Seok-Hee Hong

  • Graduate School of Informatics, Kyoto University, Kyoto, Japan

    Hiroshi Nagamochi

  • Graduate School of Informatics, Kyoto University, Japan

    Takuro Fukunaga

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation