Parameterized and Exact Computation

1. Front Matter

   PDF

2. Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters

   • Jianer Chen

   Pages 1-8

3. Algorithmic Graph Minors and Bidimensionality

   • Erik D. Demaine

   Pages 9-9

4. Algorithmic Meta-theorems

   • Stephan Kreutzer

   Pages 10-12

5. Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem

   • Omid Amini, Ignasi Sau, Saket Saurabh

   Pages 13-29

6. Fixed Structure Complexity

   • Yonatan Aumann, Yair Dombb

   Pages 30-42

7. An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees

   • Sebastian Böcker, Quang Bao Anh Bui, Anke Truss

   Pages 43-54

8. An O ^*(1.0977ⁿ) Exact Algorithm for max independent set in Sparse Graphs

   • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

   Pages 55-65

9. New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem

   • Maw-Shang Chang, Chuang-Chieh Lin, Peter Rossmanith

   Pages 66-77

10. Capacitated Domination and Covering: A Parameterized Perspective

    • Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger

    Pages 78-90

11. Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems

    • Khaled Elbassioni, Matthias Hagen, Imran Rauf

    Pages 91-102

12. A Purely Democratic Characterization of W[1]

    • Michael Fellows, Danny Hermelin, Moritz Müller, Frances Rosamond

    Pages 103-114

13. Parameterized Complexity and Approximability of the SLCS Problem

    • Sylvain Guillemot

    Pages 115-128

14. FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs

    • Sylvain Guillemot

    Pages 129-140

15. Wheel-Free Deletion Is W[2]-Hard

    • Daniel Lokshtanov

    Pages 141-147

16. Parameterized Derandomization

    • Moritz Müller

    Pages 148-159

17. A Linear Kernel for Planar Feedback Vertex Set

    • Hans L. Bodlaender, Eelko Penninkx

    Pages 160-171

18. Parameterized Chess

    • Allan Scott, Ulrike Stege

    Pages 172-189

19. The Time Complexity of Constraint Satisfaction

    • Patrick Traxler

    Pages 190-201

20. A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances

    • Magnus Wahlström

    Pages 202-213

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.

• Erfüllbarkeitsproblem der Aussagenlogik
• algorithm
• algorithmics
• algorithms
• algorithms design
• approximation
• combinatorial optimization
• complexity
• complexity theory
• computational complexity
• computational discrete mathematics
• computational graph theory
• edge dominating set
• evolutionary tree
• exact computation
• algorithm analysis and problem complexity
• data structures

Policies and ethics