Skip to main content
SpringerLink
Log in
Book cover
  • Conference proceedings
  • © 2011

Automata, Languages and Programming

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

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)

Conference series link(s): ICALP: International Colloquium on Automata, Languages, and Programming

Conference proceedings info: ICALP 2011.

Sections

Buy it now

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

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (66 papers)

  1. Front Matter

    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

    3. Approximation Schemes for Capacitated Geometric Network Design

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

  3. Session A2: Quantum Computing

    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

  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

Back to top

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.
Back to top

Keywords

Back to top

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

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

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

Search

Navigation