Parameterized and Exact Computation: Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings

✍ Scribed by Jianer Chen (auth.), Martin Grohe, Rolf Niedermeier (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2008
• Tongue: English
• Leaves: 234
• Series: Lecture Notes in Computer Science 5018 : Theoretical Computer Science and General Issues
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

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 -

✦ Subjects

Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Data Structures; Discrete Mathematics in Computer Science; Algorithms