Skip to main content
SpringerLink
Log in

Algorithms and Computation

22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings

  • Conference proceedings
  • © 2011

Overview

Editors:
  1. Takao Asano

    1. Chuo University, Tokyo, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Shin-ichi Nakano

    1. Gunma University, Kiryu-Shi, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Yoshio Okamoto

    1. Japan Advanced Institute of Science and Technology, Nomi, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Osamu Watanabe

    1. Tokyo Institute of Technology, Tokyo, Japan

    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 7074)

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

Included in the following conference series:

Conference proceedings info: ISAAC 2011.

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

  1. Front Matter

    Download chapter PDF

  3. Invited Talk II

    1. Semidefinite Programming and Approximation Algorithms: A Survey

      • Sanjeev Arora
      Pages 6-9

  4. Approximation Algorithms I

    1. The School Bus Problem on Trees

      • Adrian Bock, Elyot Grant, Jochen Könemann, Laura Sanità
      Pages 10-19

    2. Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph

      • M. Reza Khani, Mohammad R. Salavatipour
      Pages 20-29

    3. Improved Approximation Algorithms for Routing Shop Scheduling

      • Wei Yu, Guochuan Zhang
      Pages 30-39

    4. Contraction-Based Steiner Tree Approximations in Practice

      • Markus Chimani, Matthias Woste
      Pages 40-49

  5. Computational Geometry I

    1. Covering and Piercing Disks with Two Centers

      • Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin, Antoine Vigneron
      Pages 50-59

    2. Generating Realistic Roofs over a Rectilinear Polygon

      • Hee-Kap Ahn, Sang Won Bae, Christian Knauer, Mira Lee, Chan-Su Shin, Antoine Vigneron
      Pages 60-69

    3. Computing the Visibility Polygon Using Few Variables

      • Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira
      Pages 70-79

    4. Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius

      • Matias Korman
      Pages 80-89

  6. Graph Algorithms

    1. Hamiltonian Paths in the Square of a Tree

      • Jakub Radoszewski, Wojciech Rytter
      Pages 90-99

    2. Dominating Induced Matchings for P 7-free Graphs in Linear Time

      • Andreas Brandstädt, Raffaele Mosca
      Pages 100-109

    3. Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths

      • Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van ’t Hof, Marcin KamiÅ„ski, Daniël Paulusma
      Pages 110-119

    4. Recognizing Polar Planar Graphs Using New Results for Monopolarity

      • Van Bang Le, Ragnar Nevries
      Pages 120-129

    5. Robustness of Minimum Cost Arborescences

      • Naoyuki Kamiyama
      Pages 130-139

  7. Data Structures I

    1. Path Queries in Weighted Trees

      • Meng He, J. Ian Munro, Gelin Zhou
      Pages 140-149

    2. Dynamic Range Majority Data Structures

      • Amr Elmasry, Meng He, J. Ian Munro, Patrick K. Nicholson
      Pages 150-159

    3. Dynamic Range Selection in Linear Space

      • Meng He, J. Ian Munro, Patrick K. Nicholson
      Pages 160-169

    4. A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time

      • Yakov Nekrich
      Pages 170-179
Back to top

Other volumes

  1. Algorithms and Computation

Keywords

About this book

This book constitutes the refereed proceedings of the 22nd International Symposium on Algorithms and Computation, ISAAC 2011, held in Yokohama, Japan in December 2011. The 76 revised full papers presented together with two invited talks were carefully reviewed and selected from 187 submissions for inclusion in the book. This volume contains topics such as approximation algorithms; computational geometry; computational biology; computational complexity; data structures; distributed systems; graph algorithms; graph drawing and information visualization; optimization; online and streaming algorithms; parallel and external memory algorithms; parameterized algorithms; game theory and internet algorithms; randomized algorithms; and string algorithms.

Editors and Affiliations

  • Chuo University, Tokyo, Japan

    Takao Asano

  • Gunma University, Kiryu-Shi, Japan

    Shin-ichi Nakano

  • Japan Advanced Institute of Science and Technology, Nomi, Japan

    Yoshio Okamoto

  • Tokyo Institute of Technology, Tokyo, Japan

    Osamu Watanabe

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation