Ebook: Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers

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.

---

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.

---

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.
Content:
Front Matter....Pages -
On Multiway Cut Parameterized above Lower Bounds....Pages 1-12
Parameterized Complexity of Firefighting Revisited....Pages 13-26
Parameterized Complexity in Multiple-Interval Graphs: Domination....Pages 27-40
A Faster Algorithm for Dominating Set Analyzed by the Potential Method....Pages 41-54
Contracting Graphs to Paths and Trees....Pages 55-66
Increasing the Minimum Degree of a Graph by Contractions....Pages 67-79
Planar Disjoint-Paths Completion....Pages 80-93
Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing....Pages 94-105
New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree....Pages 106-117
Improved Parameterized Algorithms for above Average Constraint Satisfaction....Pages 118-131
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal....Pages 132-144
Kernel Bounds for Path and Cycle Problems....Pages 145-158
On the Hardness of Losing Width....Pages 159-168
Safe Approximation and Its Relation to Kernelization....Pages 169-180
Simpler Linear-Time Kernelization for Planar Dominating Set....Pages 181-193
Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs....Pages 194-206
Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width....Pages 207-218
Finding Good Decompositions for Dynamic Programming on Dense Graphs....Pages 219-231
Parameterized Maximum Path Coloring....Pages 232-245
On Cutwidth Parameterized by Vertex Cover....Pages 246-258
Back Matter....Pages -
Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics....Pages 259-271

---

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.
Content:
Front Matter....Pages -
On Multiway Cut Parameterized above Lower Bounds....Pages 1-12
Parameterized Complexity of Firefighting Revisited....Pages 13-26
Parameterized Complexity in Multiple-Interval Graphs: Domination....Pages 27-40
A Faster Algorithm for Dominating Set Analyzed by the Potential Method....Pages 41-54
Contracting Graphs to Paths and Trees....Pages 55-66
Increasing the Minimum Degree of a Graph by Contractions....Pages 67-79
Planar Disjoint-Paths Completion....Pages 80-93
Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing....Pages 94-105
New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree....Pages 106-117
Improved Parameterized Algorithms for above Average Constraint Satisfaction....Pages 118-131
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal....Pages 132-144
Kernel Bounds for Path and Cycle Problems....Pages 145-158
On the Hardness of Losing Width....Pages 159-168
Safe Approximation and Its Relation to Kernelization....Pages 169-180
Simpler Linear-Time Kernelization for Planar Dominating Set....Pages 181-193
Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs....Pages 194-206
Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width....Pages 207-218
Finding Good Decompositions for Dynamic Programming on Dense Graphs....Pages 219-231
Parameterized Maximum Path Coloring....Pages 232-245
On Cutwidth Parameterized by Vertex Cover....Pages 246-258
Back Matter....Pages -
Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics....Pages 259-271
....