Algorithms and Computation

1. Front Matter

   PDF

2. Invited Talk (I)

   1. Future Directions in Computer Science Research

      • John E. Hopcroft

      Pages 1-1

3. Invited Talk (II)

   1. Combinatorial Geometry and Approximation Algorithms

      • Timothy M. Chan

      Pages 2-2

4. Invited Talk (III)

   1. Origami Robots and Star Trek Replicators

      • Erik D. Demaine

      Pages 3-3

5. Graph Algorithms (I)

   1. Strong Conflict-Free Coloring for Intervals

      • Panagiotis Cheilaris, Luisa Gargano, Adele A. Rescigno, Shakhar Smorodinsky

      Pages 4-13

   2. Closing Complexity Gaps for Coloring Problems on H-Free Graphs

      • Petr A. Golovach, Daniël Paulusma, Jian Song

      Pages 14-23

   3. Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors

      • Ching-Chen Kuo, Hsueh-I Lu

      Pages 24-33

   4. Reconfiguration of List L(2,1)-Labelings in a Graph

      • Takehiro Ito, Kazuto Kawamura, Hirotaka Ono, Xiao Zhou

      Pages 34-43

6. Online and Streaming Algorithms

   1. An 8/3 Lower Bound for Online Dynamic Bin Packing

      • Prudence W. H. Wong, Fencol C. C. Yung, Mihai Burcea

      Pages 44-53

   2. Computing k-center over Streaming Data for Small k

      • Hee-Kap Ahn, Hyo-Sil Kim, Sang-Sub Kim, Wanbin Son

      Pages 54-63

   3. Precision vs Confidence Tradeoffs for ℓ2-Based Frequency Estimation in Data Streams

      • Sumit Ganguly

      Pages 64-74

   4. Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem

      • Mong-Jen Kao, Jian-Jia Chen, Ignaz Rutter, Dorothea Wagner

      Pages 75-84

7. Combinatorial Optimization (I)

   1. A Partially Ordered Structure and a Generalization of the Canonical Partition for General Graphs with Perfect Matchings

      • Nanao Kita

      Pages 85-94

   2. Fast and Simple Fully-Dynamic Cut Tree Construction

      • Tanja Hartmann, Dorothea Wagner

      Pages 95-105

   3. Green Scheduling, Flows and Matchings

      • Evripidis Bampis, Dimitrios Letsios, Giorgio Lucarelli

      Pages 106-115

   4. Popular and Clan-Popular b-Matchings

      • Katarzyna Paluch

      Pages 116-125

8. Computational Complexity (I)

   1. Kernelization and Parameterized Complexity of Star Editing and Union Editing

      • Jiong Guo, Yash Raj Shrestha

      Pages 126-135

   2. On the Advice Complexity of Buffer Management

      • Reza Dorrigiv, Meng He, Norbert Zeh

      Pages 136-145

   3. On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree

      • Tatsuya Akutsu, Takeyuki Tamura

      Pages 146-155

   4. Speeding Up Shortest Path Algorithms

      • Andrej Brodnik, Marko Grgurovič

      Pages 156-165

This book constitutes the refereed proceedings of the 23rd International Symposium on Algorithms and Computation, ISAAC 2012, held in Taipei, Taiwan, in December 2012. The 68 revised full papers presented together with three invited talks were carefully reviewed and selected from 174 submissions for inclusion in the book. This volume contains topics such as graph algorithms; online and streaming algorithms; combinatorial optimization; computational complexity; computational geometry; string algorithms; approximation algorithms; graph drawing; data structures; randomized algorithms; and algorithmic game theory.

• computational geometry
• decentralized navigation
• graphs and hypergraphs
• polynomial algorithms
• wireless networks
• algorithm analysis and problem complexity
• data structures

• Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan

  Kun-Mao Chao

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

  Tsan-sheng Hsu

• Department of Computer Science and Engineering, National Chung Hsing University, Taichung, Taiwan

  Der-Tsai Lee

Policies and ethics