Skip to main content
SpringerLink
Log in

Parameterized and Exact Computation

6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers

  • Conference proceedings
  • © 2012

Overview

Editors:
  1. Dániel Marx

    1. MTA SZTAKI, Budapest, Hungary

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Peter Rossmanith

    1. Lehrgebiet Theoretische Informatik, RWTH Aachen, Aachen, Germany

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

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

Included in the following conference series:

Conference proceedings info: IPEC 2011.

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 54.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 69.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 (21 papers)

  1. Front Matter

    Download chapter PDF

  2. On Multiway Cut Parameterized above Lower Bounds

    • Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
    Pages 1-12

  3. Parameterized Complexity of Firefighting Revisited

    • Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen
    Pages 13-26

  4. Parameterized Complexity in Multiple-Interval Graphs: Domination

    • Minghui Jiang, Yong Zhang
    Pages 27-40

  5. A Faster Algorithm for Dominating Set Analyzed by the Potential Method

    • Yoichi Iwata
    Pages 41-54

  6. Contracting Graphs to Paths and Trees

    • Pinar Heggernes, Pim van ’t Hof, Benjamin Lévêque, Daniel Lokshtanov, Christophe Paul
    Pages 55-66

  7. Increasing the Minimum Degree of a Graph by Contractions

    • Petr A. Golovach, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos
    Pages 67-79

  8. Planar Disjoint-Paths Completion

    • Isolde Adler, Stavros G. Kolliopoulos, Dimitrios M. Thilikos
    Pages 80-93

  9. Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing

    • Peter Damaschke
    Pages 94-105

  10. New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree

    • Alexander Golovnev
    Pages 106-117

  11. Improved Parameterized Algorithms for above Average Constraint Satisfaction

    • Eun Jung Kim, Ryan Williams
    Pages 118-131

  12. On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal

    • Bart M. P. Jansen, Stefan Kratsch
    Pages 132-144

  13. Kernel Bounds for Path and Cycle Problems

    • Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
    Pages 145-158

  14. On the Hardness of Losing Width

    • Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
    Pages 159-168

  15. Safe Approximation and Its Relation to Kernelization

    • Jiong Guo, Iyad Kanj, Stefan Kratsch
    Pages 169-180

  16. Simpler Linear-Time Kernelization for Planar Dominating Set

    • Torben Hagerup
    Pages 181-193

  17. Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs

    • René van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, Mathias Weller
    Pages 194-206

  18. Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width

    • Hajo Broersma, Petr A. Golovach, Viresh Patel
    Pages 207-218

  19. Finding Good Decompositions for Dynamic Programming on Dense Graphs

    • Eivind Magnus Hvidevold, Sadia Sharmin, Jan Arne Telle, Martin Vatshelle
    Pages 219-231

  20. Parameterized Maximum Path Coloring

    • Michael Lampis
    Pages 232-245
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 6th International Symposium on Parameterized and Exact Computation, IPEC 2011, in Saarbrücken, Germany, in September 2011. The 21 revised full papers presented were carefully reviewed and selected from 40 submissions. The topics addressed cover research in all aspects of parameterized and exact computation and complexity, including but 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

  • MTA SZTAKI, Budapest, Hungary

    Dániel Marx

  • Lehrgebiet Theoretische Informatik, RWTH Aachen, Aachen, Germany

    Peter Rossmanith

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation