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

Automata, Languages and Programming

37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I

Editors:

  1. Samson Abramsky

    1. Oxford University Computing Laboratory, Oxford, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Cyril Gavoille

    1. Université de Bordeaux (LaBRI) & INRIA, 351, cours de la Libération, Talence Cedex, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Claude Kirchner

    1. INRIA, Centre de Recherche Bordeaux – Sud-Ouest, 351 cours de la Libération, Talence Cedex, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Friedhelm Meyer auf der Heide

    1. Heinz Nixdorf Institute, University of Paderborn, Paderborn, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Paul G. Spirakis

    1. University of Patras and RACTI, Patras, Greece

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

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

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

  1. Front Matter

    PDF

  2. Invited Talks

    1. Local Search: Simple, Successful, But Sometimes Sluggish

      • Burkhard Monien, Dominic Dumrauf, Tobias Tscheuschner
      Pages 1-17

  3. Session 1-Track A. Combinatorial Optimization

    1. Plane Spanners of Maximum Degree Six

      • Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perković
      Pages 19-30

    2. The Positive Semidefinite Grothendieck Problem with Rank Constraint

      • Jop Briët, Fernando Mário de Oliveira Filho, Frank Vallentin
      Pages 31-42

    3. Cycle Detection and Correction

      • Amihood Amir, Estrella Eisenberg, Avivit Levy, Ely Porat, Natalie Shapira
      Pages 43-54

    4. Decomposition Width of Matroids

      • Daniel Král’
      Pages 55-66

  4. Session 2-Track A1. Game Theory

    1. The Cooperative Game Theory Foundations of Network Bargaining Games

      • MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Nicole Immorlica, Hamid Mahini
      Pages 67-78

    4. Mean-Payoff Games and Propositional Proofs

      • Albert Atserias, Elitza Maneva
      Pages 102-113

  5. Session 2-Track A2. Security

    1. Online Network Design with Outliers

      • Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski
      Pages 114-126

    2. Efficient Completely Non-malleable Public Key Encryption

      • Benoît Libert, Moti Yung
      Pages 127-139

    4. From Secrecy to Soundness: Efficient Verification via Secure Computation

      • Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
      Pages 152-163

  6. Session 3-Track A1. Data Structures

    1. Mergeable Dictionaries

      • John Iacono, Özgür Özkan
      Pages 164-175

    2. Faster Algorithms for Semi-matching Problems (Extended Abstract)

      • Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
      Pages 176-187

    3. Clustering with Diversity

      • Jian Li, Ke Yi, Qin Zhang
      Pages 188-200

  7. Session 3-Track A2. Sorting & Hashing

    1. Tight Thresholds for Cuckoo Hashing via XORSAT

      • Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink
      Pages 213-225
Back to top

Other Volumes

  1. Automata, Languages and Programming

  2. Automata, Languages and Programming

Back to top

Keywords

Back to top

Editors and Affiliations

  • Oxford University Computing Laboratory, Oxford, UK

    Samson Abramsky

  • Université de Bordeaux (LaBRI) & INRIA, 351, cours de la Libération, Talence Cedex, France

    Cyril Gavoille

  • INRIA, Centre de Recherche Bordeaux – Sud-Ouest, 351 cours de la Libération, Talence Cedex, France

    Claude Kirchner

  • Heinz Nixdorf Institute, University of Paderborn, Paderborn, Germany

    Friedhelm Meyer auf der Heide

  • University of Patras and RACTI, Patras, Greece

    Paul G. Spirakis

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