Skip to main content
SpringerLink
Log in
Book cover

Parameterized and Exact Computation

Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings

  • Conference proceedings
  • © 2006

Overview

Editors:
  1. Hans L. Bodlaender

    1. Department of Information and Computing Sciences, Utrecht University, The Netherlands

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Michael A. Langston

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 4169)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: IWPEC 2006.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (26 papers)

  1. Front Matter

    Download chapter 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
Back to top

Keywords

About this book

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.

Editors and Affiliations

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

    Hans L. Bodlaender

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

    Michael A. Langston

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation