This book constitutes the refereed proceedings of the Third International Workshop on Parameterized and Exact Computation, IWPEC 2008, held in Victoria, Canada, in May 2008 - co-located with the 40th ACM Symposium on Theory of Computing, STOC 2008.
The 17 revised full papers presented together with 3 invited lectures were carefully reviewed and selected from 32 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, parameterized complexity theory, relationship between parameterized complexity and traditional complexity classifications, applications of parameterized computation, implementation and experiments, high-performance computing and fixed-parameter tractability.
Author(s): Jianer Chen (auth.), Martin Grohe, Rolf Niedermeier (eds.)
Series: Lecture Notes in Computer Science 5018 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2008
Language: English
Pages: 227
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Data Structures; Discrete Mathematics in Computer Science; Algorithms
Front Matter....Pages -
Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters....Pages 1-8
Algorithmic Graph Minors and Bidimensionality....Pages 9-9
Algorithmic Meta-theorems....Pages 10-12
Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem....Pages 13-29
Fixed Structure Complexity....Pages 30-42
An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees....Pages 43-54
An O * (1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs....Pages 55-65
New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem....Pages 66-77
Capacitated Domination and Covering: A Parameterized Perspective....Pages 78-90
Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems....Pages 91-102
A Purely Democratic Characterization of W[1]....Pages 103-114
Parameterized Complexity and Approximability of the SLCS Problem....Pages 115-128
FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs....Pages 129-140
Wheel-Free Deletion Is W [2]-Hard....Pages 141-147
Parameterized Derandomization....Pages 148-159
A Linear Kernel for Planar Feedback Vertex Set....Pages 160-171
Parameterized Chess....Pages 172-189
The Time Complexity of Constraint Satisfaction....Pages 190-201
A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances....Pages 202-213
Exact Algorithms for Edge Domination....Pages 214-225
Back Matter....Pages -
