Skip to main content
SpringerLink
Log in

Parameterized and Exact Computation

8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers

  • Conference proceedings
  • © 2013

Overview

Editors:
  1. Gregory Gutin

    1. Royal Holloway, University of London, Egham, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Stefan Szeider

    1. Institute of Information Systems, Vienna University of Technology, Vienna, Austria

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • High quality selected papers
  • Up to date results
  • State of the art research

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

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

Included in the following conference series:

Conference proceedings info: IPEC 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 (30 papers)

  1. Front Matter

    Download chapter PDF

  2. Exact Complexity and Satisfiability

    • Russell Impagliazzo, Ramamohan Paturi
    Pages 1-3

  3. The Parameterized Complexity of Fixpoint Free Elements and Bases in Permutation Groups

    • Vikraman Arvind
    Pages 4-15

  4. Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints

    • Rémy Belmonte, Petr A. Golovach, Pim van ’t Hof, Daniël Paulusma
    Pages 16-27

  5. Declarative Dynamic Programming as an Alternative Realization of Courcelle’s Theorem

    • Bernhard Bliem, Reinhard Pichler, Stefan Woltran
    Pages 28-40

  6. The Fine Details of Fast Dynamic Programming over Tree Decompositions

    • Hans L. Bodlaender, Paul Bonsma, Daniel Lokshtanov
    Pages 41-53

  7. On Subexponential and FPT-Time Inapproximability

    • Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, Vangelis Th. Paschos
    Pages 54-65

  8. Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization

    • Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Émeric Tourniaire
    Pages 66-77

  9. Chain Minors Are FPT

    • JarosÅ‚aw BÅ‚asiok, M. KamiÅ„ski
    Pages 78-83

  10. Incompressibility of H-Free Edge Modification

    • Leizhen Cai, Yufei Cai
    Pages 84-96

  11. Contracting Few Edges to Remove Forbidden Induced Subgraphs

    • Leizhen Cai, Chengwei Guo
    Pages 97-109

  12. Fixed-Parameter and Approximation Algorithms: A New Look

    • Rajesh Chitnis, MohammadTaghi Hajiaghayi, Guy Kortsarz
    Pages 110-122

  13. Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs

    • Mateus de Oliveira Oliveira
    Pages 123-136

  14. Computing Tree-Depth Faster Than 2n

    • Fedor V. Fomin, Archontia C. Giannopoulou, MichaÅ‚ Pilipczuk
    Pages 137-149

  15. Faster Exact Algorithms for Some Terminal Set Problems

    • Rajesh Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
    Pages 150-162

  16. Parameterized Algorithms for Modular-Width

    • Jakub Gajarský, Michael Lampis, Sebastian Ordyniak
    Pages 163-176

  17. A Faster FPT Algorithm for Bipartite Contraction

    • Sylvain Guillemot, Dániel Marx
    Pages 177-188

  18. On the Ordered List Subgraph Embedding Problems

    • Olawale Hassan, Iyad Kanj, Daniel Lokshtanov, Ljubomir Perković
    Pages 189-201

  19. A Completeness Theory for Polynomial (Turing) Kernelization

    • Danny Hermelin, Stefan Kratsch, Karolina SoÅ‚tys, Magnus Wahlström, Xi Wu
    Pages 202-215

  20. On Sparsification for Computing Treewidth

    • Bart M. P. Jansen
    Pages 216-229
Back to top

Other volumes

  1. Parameterized and Exact Computation

Keywords

About this book

This book constitutes the thoroughly refereed post-conference proceedings of the 8th International Symposium on Parameterized and Exact Computation, IPEC 2013, in Sophia Antipolis, France, in September 2013.
The 29 revised full papers presented were carefully reviewed and selected from 58 submissions. The topics addressed cover research in all aspects of parameterized/exact algorithms and complexity including but are not limited to new techniques for the design and analysis of parameterized and exact algorithms, fixed-parameter tractability results, parameterized complexity theory, relationship between parameterized complexity and traditional complexity classifications, applications of parameterized and exact computation, and implementation issues of parameterized and exact algorithms.

Editors and Affiliations

  • Royal Holloway, University of London, Egham, UK

    Gregory Gutin

  • Institute of Information Systems, Vienna University of Technology, Vienna, Austria

    Stefan Szeider

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation