Skip to main content
SpringerLink
Log in
SpringerLink
Log in

Automata, Languages and Programming

38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011. Proceedings, Part I

  • Conference proceedings
  • © 2011

Overview

Editors:
  1. Luca Aceto

    1. ICE-TCS, School of Computer Science, Reykjavik University, Reykjavik, Iceland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Monika Henzinger

    1. Fakultät für Informatik, Universität Wien, Wien, Austria

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Jiří Sgall

    1. Department of Applied Mathematics, Charles University, Praha 1, Czech Republic

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

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

Included in the following conference series:

Conference proceedings info: ICALP 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 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 (66 papers)

  1. Front Matter

    Download chapter PDF

  2. Session A1: Network Design Problems

    1. Improved Approximation for the Directed Spanner Problem

      • Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
      Pages 1-12

    2. An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity

      • Bundit Laekhanukit
      Pages 13-24

    3. Approximation Schemes for Capacitated Geometric Network Design

      • Anna Adamaszek, Artur Czumaj, Andrzej Lingas, Jakub Onufry Wojtaszczyk
      Pages 25-36

    4. An O(logn)-Competitive Algorithm for Online Constrained Forest Problems

      • Jiawei Qian, David P. Williamson
      Pages 37-48

  3. Session A2: Quantum Computing

    1. On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity

      • Shengyu Zhang
      Pages 49-60

    2. Advice Coins for Classical and Quantum Computation

      • Scott Aaronson, Andrew Drucker
      Pages 61-72

    3. Quantum Commitments from Complexity Assumptions

      • André Chailloux, Iordanis Kerenidis, Bill Rosgen
      Pages 73-85

    4. Limitations on Quantum Dimensionality Reduction

      • Aram W. Harrow, Ashley Montanaro, Anthony J. Short
      Pages 86-97

  4. Session A3: Graph Algorithms

    1. On Tree-Constrained Matchings and Generalizations

      • Stefan Canzar, Khaled Elbassioni, Gunnar W. Klau, Julián Mestre
      Pages 98-109

    2. Tight Bounds for Linkages in Planar Graphs

      • Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, Dimitrios Thilikos
      Pages 110-121

    3. A Tighter Insertion-Based Approximation of the Crossing Number

      • Markus Chimani, Petr Hliněný
      Pages 122-134

    4. Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs

      • Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer
      Pages 135-146

  5. Session A4: Games, Approximation Schemes, Smoothed Analysis

    1. Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes

      • Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey
      Pages 147-158

    2. Pairwise-Interaction Games

      • Martin Dyer, Velumailum Mohanaraj
      Pages 159-170

    3. Settling the Complexity of Local Max-Cut (Almost) Completely

      • Robert Elsässer, Tobias Tscheuschner
      Pages 171-182

    4. Clique Clustering Yields a PTAS for max-Coloring Interval Graphs

      • Tim Nonner
      Pages 183-194

  6. Session A5: Online Algorithms

    1. On Variants of File Caching

      • Leah Epstein, Csanád Imreh, Asaf Levin, Judit Nagy-György
      Pages 195-206

    2. On the Advice Complexity of the k-Server Problem

      • Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič
      Pages 207-218

    3. Sleep Management on Multiple Machines for Energy and Flow Time

      • Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee, Chi-Man Liu, Hing-Fung Ting
      Pages 219-231
Back to top

Other volumes

  1. Automata, Languages and Programming

  2. Automata, Languages and Programming

Keywords

About this book

The two-volume set LNCS 6755 and LNCS 6756 constitutes the refereed proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, held in Zürich, Switzerland, in July 2011. The 114 revised full papers (68 papers for track A, 29 for track B, and 17 for track C) presented together with 4 invited talks, 3 best student papers, and 3 best papers were carefully reviewed and selected from a total of 398 submissions. The papers are grouped in three major tracks on algorithms, complexity and games; on logic, semantics, automata, and theory of programming; as well as on foundations of networked computation: models, algorithms and information management.

Editors and Affiliations

  • ICE-TCS, School of Computer Science, Reykjavik University, Reykjavik, Iceland

    Luca Aceto

  • Fakultät für Informatik, Universität Wien, Wien, Austria

    Monika Henzinger

  • Department of Applied Mathematics, Charles University, Praha 1, Czech Republic

    Jiří Sgall

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation