Skip to main content
SpringerLink
Log in
Book cover

Algorithms and Computation

23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings

  • Conference proceedings
  • © 2012

Overview

Editors:
  1. Kun-Mao Chao

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Tsan-sheng Hsu

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Der-Tsai Lee

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Up to date results
  • Fast track conference proceedings
  • State of the art research

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 7676)

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

Included in the following conference series:

Conference proceedings info: ISAAC 2012.

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

  1. Front Matter

    Download chapter 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
Back to top

Other volumes

  1. Algorithms and Computation

Keywords

About this book

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.

Editors and Affiliations

  • 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

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation