Algorithms and Computation

1. Front Matter

   PDF

2. Invited Talk

   1. Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?

      • Tetsuo Asano

      Pages 1-1

   2. Some Constrained Notions of Planarity

      • Peter Eades

      Pages 2-2

   3. Reachability Problems on Directed Graphs

      • Robert E. Tarjan

      Pages 3-3

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

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.

• AAC
• algorithms
• complexity
• computational geometry
• data structure
• database
• game theory
• optimization
• data structures
• algorithm analysis and problem complexity

• 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

Policies and ethics