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

Automata, Languages, and Programming

40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I

Editors:

  1. Fedor V. Fomin

    1. Department of Informatics, University of Bergen, Bergen, Norway

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rūsiņš Freivalds

    1. Faculty of Computing, University of Latvia, Riga, Latvia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Marta Kwiatkowska

    1. Department of Computer Science, University of Oxford, Oxford, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. David Peleg

    1. Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • State-of-the-art research
  • Fast-track conference proceedings
  • Unique visibility

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

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

Sections

Buy it now

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

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

Table of contents (71 papers)

  1. Front Matter

    PDF

  2. Track A – Algorithms, Complexity and Games

    1. Exact Weight Subgraphs and the k-Sum Conjecture

      • Amir Abboud, Kevin Lewi
      Pages 1-12

    2. Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines

      • S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar
      Pages 13-24

    3. Tight Lower Bound for Linear Sketches of Moments

      • Alexandr Andoni, Huy L. Nguyễn, Yury Polyanskiy, Yihong Wu
      Pages 25-32

    4. Optimal Partitioning for Dual Pivot Quicksort

      • Martin Aumüller, Martin Dietzfelbinger
      Pages 33-44

    5. Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm

      • Per Austrin, Petteri Kaski, Mikko Koivisto, Jussi Määttä
      Pages 45-56

    6. On the Extension Complexity of Combinatorial Polytopes

      • David Avis, Hans Raj Tiwary
      Pages 57-68

    7. Algorithms for Hub Label Optimization

      • Maxim Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan
      Pages 69-80

    8. Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems

      • MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Vahid Liaghat
      Pages 81-92

    9. Search-Space Size in Contraction Hierarchies

      • Reinhard Bauer, Tobias Columbus, Ignaz Rutter, Dorothea Wagner
      Pages 93-104

    10. Time-Efficient Quantum Walks for 3-Distinctness

      • Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
      Pages 105-122

    11. An Algebraic Characterization of Testable Boolean CSPs

      • Arnab Bhattacharyya, Yuichi Yoshida
      Pages 123-134

    12. Approximation Algorithms for the Joint Replenishment Problem with Deadlines

      • Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil Dobbs, Tomasz Nowicki, Maxim Sviridenko et al.
      Pages 135-147

    13. Sparse Suffix Tree Construction in Small Space

      • Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj
      Pages 148-159

    14. Tree Compression with Top Trees

      • Philip Bille, Inge Li Gørtz, Gad M. Landau, Oren Weimann
      Pages 160-171

    15. Noncommutativity Makes Determinants Hard

      • Markus Bläser
      Pages 172-183

    16. Optimal Orthogonal Graph Drawing with Convex Bend Costs

      • Thomas Bläsius, Ignaz Rutter, Dorothea Wagner
      Pages 184-195

    17. Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth

      • Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
      Pages 196-207

    18. On the Complexity of Higher Order Abstract Voronoi Diagrams

      • Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, Maksym Zavershynskyi
      Pages 208-219

    19. A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions

      • Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino
      Pages 220-231
Back to top

Other Volumes

  1. Automata, Languages, and Programming

  2. Automata, Languages, and Programming

Back to top

About this book

This two-volume set of LNCS 7965 and LNCS 7966 constitutes the refereed proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, held in Riga, Latvia, in July 2013. The total of 124 revised full papers presented were carefully reviewed and selected from 422 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation.
Back to top

Keywords

Back to top

Editors and Affiliations

  • Department of Informatics, University of Bergen, Bergen, Norway

    Fedor V. Fomin

  • Faculty of Computing, University of Latvia, Riga, Latvia

    Rūsiņš Freivalds

  • Department of Computer Science, University of Oxford, Oxford, UK

    Marta Kwiatkowska

  • Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

    David Peleg

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

Search

Navigation