𝔖 Scriptorium
✦   LIBER   ✦

πŸ“

Parameterized and Exact Computation: Second International Workshop, IWPEC 2006, ZΓΌrich, Switzerland, September 13-15, 2006. Proceedings

✍ Scribed by FÑbio Protti, Maise Dantas da Silva (auth.), Hans L. Bodlaender, Michael A. Langston (eds.)


Publisher
Springer-Verlag Berlin Heidelberg
Year
2006
Tongue
English
Leaves
288
Series
Lecture Notes in Computer Science 4169 : Theoretical Computer Science and General Issues
Edition
1
Category
Library

⬇  Acquire This Volume

No coin nor oath required. For personal study only.

✦ Synopsis


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.

✦ Table of Contents


Front Matter....Pages -
Applying Modular Decomposition to Parameterized Bicluster Editing....Pages 1-12
The Cluster Editing Problem: Implementations and Experiments....Pages 13-24
The Parameterized Complexity of Maximality and Minimality Problems....Pages 25-37
Parameterizing MAX SNP Problems Above Guaranteed Values....Pages 38-49
Randomized Approximations of Parameterized Counting Problems....Pages 50-59
Fixed-Parameter Complexity of Minimum Profile Problems....Pages 60-71
On the OBDD Size for Graphs of Bounded Tree- and Clique-Width....Pages 72-83
Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms....Pages 84-95
Fixed-Parameter Approximation: Conceptual Framework and Approximability Results....Pages 96-108
On Parameterized Approximability....Pages 109-120
Parameterized Approximation Problems....Pages 121-129
An Exact Algorithm for the Minimum Dominating Clique Problem....Pages 130-141
edge dominating set : Efficient Enumeration-Based Exact Algorithms....Pages 142-153
Parameterized Complexity of Independence and Domination on Geometric Graphs....Pages 154-165
Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs....Pages 166-174
On the Parameterized Complexity of d -Dimensional Point Set Pattern Matching....Pages 175-183
Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$ ....Pages 184-191
The Undirected Feedback Vertex Set Problem Has a Poly( k ) Kernel....Pages 192-202
Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual....Pages 203-214
On the Effective Enumerability of NP Problems....Pages 215-226
The Parameterized Complexity of Enumerating Frequent Itemsets....Pages 227-238
Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems....Pages 239-250
Towards a Taxonomy of Techniques for Designing Parameterized Algorithms....Pages 251-263
Kernels: Annotated, Proper and Induced....Pages 264-275
The Lost Continent of Polynomial Time: Preprocessing and Kernelization....Pages 276-277
FPT at Work: Using Fixed Parameter Tractability to Solve Larger Instances of Hard Problems....Pages 278-278
Back Matter....Pages -

✦ Subjects


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


πŸ“œ SIMILAR VOLUMES


Parameterized and Exact Computation: Sec
✍ Hans L. Bodlaender πŸ“‚ Library πŸ“… 2006 πŸ› Springer 🌐 English

<span>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 i

Parameterized and Exact Computation: Fir
✍ Peter Damaschke (auth.), Rod Downey, Michael Fellows, Frank Dehne (eds.) πŸ“‚ Library πŸ“… 2004 πŸ› Springer-Verlag Berlin Heidelberg 🌐 English

<P>This book constitutes the refereed proceedings of the First International Workshop on Parameterized and Exact Computation, IWPEC 2004, held in Bergen, Norway, in September 2004.</P><P>The 25 revised full papers presented together with an invited paper were carefully reviewed and selected from 47

Parameterized and Exact Computation: Thi
✍ Jianer Chen (auth.), Martin Grohe, Rolf Niedermeier (eds.) πŸ“‚ Library πŸ“… 2008 πŸ› Springer-Verlag Berlin Heidelberg 🌐 English

<p><P>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.</P><P>The 17 revised full papers presented to

Parameterized and Exact Computation: 4th
✍ Noga Alon, Shai Gutner (auth.), Jianer Chen, Fedor V. Fomin (eds.) πŸ“‚ Library πŸ“… 2009 πŸ› Springer-Verlag Berlin Heidelberg 🌐 English

<P>This book constitutes the refereed best selected papers of the 4th International Workshop on Parameterized and Exact Computation, IWPEC 2009, held in Copenhagen, Denmark, in September 2009.</P><P>The 25 revised full papers presented together with 2 invited talks were carefully reviewed and select

Parameterized and Exact Computation: 4th
✍ Noga Alon, Shai Gutner (auth.), Jianer Chen, Fedor V. Fomin (eds.) πŸ“‚ Library πŸ“… 2009 πŸ› Springer-Verlag Berlin Heidelberg 🌐 English

<P>This book constitutes the refereed best selected papers of the 4th International Workshop on Parameterized and Exact Computation, IWPEC 2009, held in Copenhagen, Denmark, in September 2009.</P><P>The 25 revised full papers presented together with 2 invited talks were carefully reviewed and select