Skip to main content
SpringerLink
Log in
Book cover

Parameterized and Exact Computation

9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers

  • Conference proceedings
  • © 2014

Overview

Editors:
  1. Marek Cygan

    1. Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Warsaw, Poland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Pinar Heggernes

    1. University of Bergen, Bergen, Norway

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

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

Included in the following conference series:

Conference proceedings info: IPEC 2014.

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 EPUB and 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 (28 papers)

  1. Front Matter

    Pages I-IX
    Download chapter PDF

  2. Lower Bounds for Kernelization

    • Hans L. Bodlaender
    Pages 1-14

  3. On the Parameterized Complexity of Associative and Commutative Unification

    • Tatsuya Akutsu, Jesper Jansson, Atsuhiro Takasu, Takeyuki Tamura
    Pages 15-27

  4. On Polynomial Kernelization of \(\mathcal {H}\)-free Edge Deletion

    • N. R. Aravind, R. B. Sandeep, Naveen Sivadasan
    Pages 28-38

  5. Solving Linear Equations Parameterized by Hamming Weight

    • Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán
    Pages 39-50

  6. The Parameterized Complexity of Geometric Graph Isomorphism

    • Vikraman Arvind, Gaurav Rattan
    Pages 51-62

  7. The Role of Planarity in Connectivity Problems Parameterized by Treewidth

    • Julien Baste, Ignasi Sau
    Pages 63-74

  8. Parameterized Inapproximability of Degree Anonymization

    • Cristina Bazgan, André Nichterlein
    Pages 75-84

  9. The \(k\)-Distinct Language: Parameterized Automata Constructions

    • Ran Ben-Basat, Ariel Gabizon, Meirav Zehavi
    Pages 85-96

  10. A \(14k\)-Kernel for Planar Feedback Vertex Set via Region Decomposition

    • Marthe Bonamy, Łukasz Kowalik
    Pages 97-109

  11. The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration

    • Paul Bonsma, Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman
    Pages 110-121

  12. Quantified Conjunctive Queries on Partially Ordered Sets

    • Simone Bova, Robert Ganian, Stefan Szeider
    Pages 122-134

  13. Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree

    • Jannis Bulian, Anuj Dawar
    Pages 135-146

  14. Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size

    • Mathieu Chapelle, Manfred Cochefert, Dieter Kratsch, Romain Letourneur, Mathieu Liedloff
    Pages 147-158

  15. A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

    • Rajesh Hemant Chitnis, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Saeed Seddighin
    Pages 159-171

  16. The Firefighter Problem: A Structural Analysis

    • Janka Chlebíková, Morgan Chopin
    Pages 172-183

  17. AND-compression of NP-complete Problems: Streamlined Proof and Minor Observations

    • Holger Dell
    Pages 184-195

  18. Editing to a Graph of Given Degrees

    • Petr A. Golovach
    Pages 196-207

  19. Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem

    • Gregory Gutin, Stefan Kratsch, Magnus Wahlström
    Pages 208-220

  20. Finding Shortest Paths Between Graph Colourings

    • Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
    Pages 221-233
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 9th International Symposium on Parameterized and Exact Computation, IPEC 2014, in Wroclaw, Poland, in September 2014. The 27 revised full papers presented together with one invited paper were carefully reviewed and selected from 42 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 exponential-time computation; and implementation issues of parameterized and exact exponential-time algorithms.

Editors and Affiliations

  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Warsaw, Poland

    Marek Cygan

  • University of Bergen, Bergen, Norway

    Pinar Heggernes

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation