Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers

✍ Scribed by Russell Impagliazzo, Ramamohan Paturi (auth.), Gregory Gutin, Stefan Szeider (eds.)

• Publisher: Springer International Publishing
• Year: 2013
• Tongue: English
• Leaves: 385
• Series: Lecture Notes in Computer Science 8246 Theoretical Computer Science and General Issues
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Front Matter....Pages -
Exact Complexity and Satisfiability....Pages 1-3
The Parameterized Complexity of Fixpoint Free Elements and Bases in Permutation Groups....Pages 4-15
Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints....Pages 16-27
Declarative Dynamic Programming as an Alternative Realization of Courcelle’s Theorem....Pages 28-40
The Fine Details of Fast Dynamic Programming over Tree Decompositions....Pages 41-53
On Subexponential and FPT-Time Inapproximability....Pages 54-65
Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization....Pages 66-77
Chain Minors Are FPT....Pages 78-83
Incompressibility of H -Free Edge Modification....Pages 84-96
Contracting Few Edges to Remove Forbidden Induced Subgraphs....Pages 97-109
Fixed-Parameter and Approximation Algorithms: A New Look....Pages 110-122
Subgraphs Satisfying MSO Properties on z -Topologically Orderable Digraphs....Pages 123-136
Computing Tree-Depth Faster Than 2 n ....Pages 137-149
Faster Exact Algorithms for Some Terminal Set Problems....Pages 150-162
Parameterized Algorithms for Modular-Width....Pages 163-176
A Faster FPT Algorithm for Bipartite Contraction....Pages 177-188
On the Ordered List Subgraph Embedding Problems....Pages 189-201
A Completeness Theory for Polynomial (Turing) Kernelization....Pages 202-215
On Sparsification for Computing Treewidth....Pages 216-229
The Jump Number Problem: Exact and Parameterized....Pages 230-242
On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges....Pages 243-254
Hardness of r - dominating set on Graphs of Diameter ( r  + 1)....Pages 255-267
Amalgam Width of Matroids....Pages 268-280
On the Parameterized Complexity of Reconfiguration Problems....Pages 281-294
FPT Algorithms for Consecutive Ones Submatrix Problems....Pages 295-307
Upper Bounds on Boolean-Width with Applications to Exact Algorithms....Pages 308-320
Speeding Up Dynamic Programming with Representative Sets....Pages 321-334
Completeness Results for Parameterized Space Classes....Pages 335-347
Treewidth and Pure Nash Equilibria....Pages 348-360
Algorithms for k -Internal Out-Branching....Pages 361-373
Back Matter....Pages -

✦ Subjects

Algorithm Analysis and Problem Complexity; Algorithms; Numeric Computing; Discrete Mathematics in Computer Science; Data Structures; Math Applications in Computer Science