Parameterized and Exact Computation

1. Front Matter

   PDF

2. Applying Modular Decomposition to Parameterized Bicluster Editing

   • Fábio Protti, Maise Dantas da Silva, Jayme Luiz Szwarcfiter

   Pages 1-12

3. The Cluster Editing Problem: Implementations and Experiments

   • Frank Dehne, Michael A. Langston, Xuemei Luo, Sylvain Pitre, Peter Shaw, Yun Zhang

   Pages 13-24

4. The Parameterized Complexity of Maximality and Minimality Problems

   • Yijia Chen, Jörg Flum

   Pages 25-37

5. Parameterizing MAX SNP Problems Above Guaranteed Values

   • Meena Mahajan, Venkatesh Raman, Somnath Sikdar

   Pages 38-49

6. Randomized Approximations of Parameterized Counting Problems

   • Moritz Müller

   Pages 50-59

7. Fixed-Parameter Complexity of Minimum Profile Problems

   • Gregory Gutin, Stefan Szeider, Anders Yeo

   Pages 60-71

8. On the OBDD Size for Graphs of Bounded Tree- and Clique-Width

   • Klaus Meer, Dieter Rautenbach

   Pages 72-83

9. Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms

   • Yang Liu, Songjian Lu, Jianer Chen, Sing-Hoi Sze

   Pages 84-95

10. Fixed-Parameter Approximation: Conceptual Framework and Approximability Results

    • Liming Cai, Xiuzhen Huang

    Pages 96-108

11. On Parameterized Approximability

    • Yijia Chen, Martin Grohe, Magdalena Grüber

    Pages 109-120

12. Parameterized Approximation Problems

    • Rodney G. Downey, Michael R. Fellows, Catherine McCartin

    Pages 121-129

13. An Exact Algorithm for the Minimum Dominating Clique Problem

    • Dieter Kratsch, Mathieu Liedloff

    Pages 130-141

14. edge dominating set: Efficient Enumeration-Based Exact Algorithms

    • Henning Fernau

    Pages 142-153

15. Parameterized Complexity of Independence and Domination on Geometric Graphs

    • Dániel Marx

    Pages 154-165

16. Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs

    • Jan Kára, Jan Kratochvíl

    Pages 166-174

17. On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching

    • Sergio Cabello, Panos Giannopoulos, Christian Knauer

    Pages 175-183

18. Finding a Minimum Feedback Vertex Set in Time \(\mathcal{O} (1.7548^n)\)

    • Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin

    Pages 184-191

19. The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel

    • Kevin Burrage, Vladimir Estivill-Castro, Michael Fellows, Michael Langston, Shev Mac, Frances Rosamond

    Pages 192-202

20. Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual

    • Jiong Guo, Rolf Niedermeier, Sebastian Wernicke

    Pages 203-214

The Second International Workshop on Parameterized and Exact Computation (IWPEC) was held in Zu ¨rich, Switzerland, during September 13–15, 2006. It th was organized as a component of ALGO 2006, which also hosted the 14 - th nual European Symposium on Algorithms, the 6 Workshop on Algorithms in th Bioinformatics, the 4 Workshop on Approximation and Online Algorithms, th and the 6 Workshop on Algorithmic Methods and Models for Optimization of Railways. This meeting was the second in the IWPEC series, with the ?rst having been held in Bergen, Norway, during September 14–16, 2004. The ?eld continues to experience rapid growth, in part due to its appeal as an alternative to tra- tional complexity theory, and in part due to the powerful practical applications it has spawned. IWPEC events are intended to cover research in all aspects of parameterizedand exact computation and complexity, including but not limited to new techniques for the design and analysis of parameterized and exact al- rithms, parameterized complexity theory, relationships between parameterized complexity and traditional complexity, applications of parameterized and exact computation, implementation issues and high-performance computing. A major goal is to disseminate the latest research results, including signi?cant work-- progress, and to identify, de?ne and explore directions for future study. The papers accepted for presentation and printed in these proceedings rep- sent a diverse spectrum of the latest developments on parameterized and exact algorithm design, analysis, application and implementation.

• algorithmics
• algorithms
• algorithms design
• approximation
• combinatorial optimization
• complexity analysis
• computational complexity
• computational discrete mathematics
• computational geometry
• computational graph theory
• exact computation
• geometric alg
• algorithm analysis and problem complexity
• data structures

• Department of Information and Computing Sciences, Utrecht University, The Netherlands

  Hans L. Bodlaender

• University of Tennessee, Knoxville, Tennessee, U.S.A.

  Michael A. Langston

Policies and ethics