Skip to main content
SpringerLink
Log in
Book cover

Algorithms and Complexity

8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings

  • Conference proceedings
  • © 2013

Overview

Editors:
  1. Paul G. Spirakis

    1. School of Engineering, Department of Computer Engineering and Informatics, University of Patras, Patras, Greece

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Maria Serna

    1. LSI Department, Edif Omega, Universitat Politècnica de Catalunya, Barcelona, Spain

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Fast track conference proceedings
  • State-of-the-art research
  • Up to date results

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

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

Included in the following conference series:

Conference proceedings info: CIAC 2013.

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

Licence this eBook for your library

Institutional subscriptions

Table of contents (31 papers)

  1. Front Matter

    Download chapter PDF

  2. Approximation Algorithms for Disjoint st-Paths with Minimum Activation Cost

    • Hasna Mohsen Alqahtani, Thomas Erlebach
    Pages 1-12

  3. Parameterized Complexity and Kernel Bounds for Hard Planning Problems

    • Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider
    Pages 13-24

  4. Selfish Resource Allocation in Optical Networks

    • Evangelos Bampas, Aris Pagourtzis, George Pierrakos, Vasilis Syrgkanis
    Pages 25-36

  5. Average Optimal String Matching in Packed Strings

    • Djamal Belazzougui, Mathieu Raffinot
    Pages 37-48

  6. Parameterized Complexity of DAG Partitioning

    • René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein et al.
    Pages 49-60

  7. Four Measures of Nonlinearity

    • Joan Boyar, Magnus Find, René Peralta
    Pages 61-72

  8. On the Characterization of Plane Bus Graphs

    • Till Bruckdorfer, Stefan Felsner, Michael Kaufmann
    Pages 73-84

  9. Online Multi-dimensional Dynamic Bin Packing of Unit-Fraction Items

    • Mihai Burcea, Prudence W. H. Wong, Fencol C. C. Yung
    Pages 85-96

  10. A Greedy Approximation Algorithm for Minimum-Gap Scheduling

    • Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor
    Pages 97-109

  11. Exponential Complexity of Satisfiability Testing for Linear-Size Boolean Formulas

    • Evgeny Dantsin, Alexander Wolpert
    Pages 110-121

  12. Linear Time Distributed Swap Edge Algorithms

    • Ajoy K. Datta, Lawrence L. Larmore, Linda Pagli, Giuseppe Prencipe
    Pages 122-133

  13. Decentralized Throughput Scheduling

    • Jasper de Jong, Marc Uetz, Andreas Wombacher
    Pages 134-145

  14. New Results on Stabbing Segments with a Polygon

    • José Miguel Díaz-Báñez, Matias Korman, Pablo Pérez-Lantero, Alexander Pilz, Carlos Seara, Rodrigo I. Silveira
    Pages 146-157

  15. Improving the H k -Bound on the Price of Stability in Undirected Shapley Network Design Games

    • Yann Disser, Andreas Emil Feldmann, Max Klimm, Matúš Mihalák
    Pages 158-169

  16. Complexity of Barrier Coverage with Relocatable Sensors in the Plane

    • Stefan Dobrev, Stephane Durocher, Mohsen Eftekhari, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc et al.
    Pages 170-182

  17. Succinct Permanent Is NEXP-Hard with Many Hard Instances

    • Shlomi Dolev, Nova Fandina, Dan Gutfreund
    Pages 183-196

  18. Money-Based Coordination of Network Packets

    • Pavlos S. Efraimidis, Remous-Aris Koutsiamanis
    Pages 197-208

  19. Truthful Many-to-Many Assignment with Private Weights

    • Bruno Escoffier, Jérôme Monnot, Fanny Pascual, Olivier Spanjaard
    Pages 209-220

  20. Competitive Online Clique Clustering

    • Aleksander Fabijan, Bengt J. Nilsson, Mia Persson
    Pages 221-233
Back to top

Other volumes

  1. Algorithms and Complexity

Keywords

About this book

This book constitutes the refereed conference proceedings of the 8th International Conference on Algorithms and Complexity, CIAC 2013, held in Barcelona, Spain, during May 22-24, 2013. The 31 revised full papers presented were carefully reviewed and selected from 75 submissions. The papers present current research in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures.

Editors and Affiliations

  • School of Engineering, Department of Computer Engineering and Informatics, University of Patras, Patras, Greece

    Paul G. Spirakis

  • LSI Department, Edif Omega, Universitat Politècnica de Catalunya, Barcelona, Spain

    Maria Serna

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation