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

Automata, Languages and Programming

34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings

Editors:

  1. Lars Arge
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Christian Cachin
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Tomasz Jurdziński
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Andrzej Tarlecki
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

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

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 2007.

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

  1. Front Matter

    PDF

  2. Invited Lectures

    1. Ushering in a New Era of Algorithm Design

      • Bernard Chazelle
      Pages 1-1

    4. Subexponential Parameterized Algorithms

      • Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos
      Pages 15-27

  3. Session A1

    1. Competitive Algorithms for Due Date Scheduling

      • Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs
      Pages 28-39

    2. Mechanism Design for Fractional Scheduling on Unrelated Machines

      • George Christodoulou, Elias Koutsoupias, Annamária Kovács
      Pages 40-52

  4. Session A2

    1. Estimating Sum by Weighted Sampling

      • Rajeev Motwani, Rina Panigrahy, Ying Xu
      Pages 53-64

  5. Session A3

    1. Low Distortion Spanners

      • Seth Pettie
      Pages 78-89

    2. Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs

      • André Berger, Michelangelo Grigni
      Pages 90-101

    3. Labeling Schemes for Vertex Connectivity

      • Amos Korman
      Pages 102-109

  6. Session A4

    1. Unbounded-Error One-Way Classical and Quantum Communication Complexity

      • Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita
      Pages 110-121

    2. A Lower Bound on Entanglement-Assisted Quantum Communication Complexity

      • Ashley Montanaro, Andreas Winter
      Pages 122-133

    3. Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity

      • Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel
      Pages 134-145

  7. Session A5

    1. An Optimal Decomposition Algorithm for Tree Edit Distance

      • Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
      Pages 146-157

    2. On Commutativity Based Edge Lean Search

      • Dragan Bošnački, Edith Elkind, Blaise Genest, Doron Peled
      Pages 158-170

    3. Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems

      • Irit Katriel, Claire Kenyon-Mathieu, Eli Upfal
      Pages 171-182

  8. Session A6

    1. On the Complexity of Hard-Core Set Constructions

      • Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu
      Pages 183-194

    2. Approximation by DNF: Examples and Counterexamples

      • Ryan O’Donnell, Karl Wimmer
      Pages 195-206
Back to top

Other Volumes

  1. Automata, Languages and Programming

Back to top

Keywords

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