Parameterized and Exact Computation

by Chen, Jianer; Fomin, Fedor V.

• ISBN13: 9783642112683
• ISBN10: 3642112684
• Format: Paperback
• Copyright: 2010-02-19
• Publisher: Springer-Verlag New York Inc

Summary

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.The 25 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 52 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 and exact computation, implementation issues of parameterized and exact algorithms, high-performance computing and fixed-parameter tractability.

Table of Contents

Balanced Hashing, Color Coding and Approximate Counting (Invited Talk)	p. 1
Kernelization: New Upper and Lower Bound Techniques (Invited Talk)	p. 17
A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams	p. 38
Planar Capacitated Dominating Set Is W [1]-Hard	p. 50
Boolean-Width of Graphs	p. 61
The Complexity of Satisfiability of Small Depth Circuits	p. 75
On Finding Directed Trees with Many Leaves	p. 86
Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms	p. 98
Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover	p. 110
What Makes Equitable Connected Partition Easy	p. 122
Improved Induced Matchings in Sparse Graphs	p. 134
Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs	p. 149
An Exact Algorithm for the Maximum Leaf Spanning Tree Problem	p. 161
An Exponential Time 2-Approximation Algorithm for Bandwidth	p. 173
On Digraph Width Measures in Parameterized Algorithmics	p. 185
The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension	p. 198
Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms	p. 210
Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs	p. 222
A Probabilistic Approach to Problems Parameterized above or below Tight Bounds	p. 234
Polynomical Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor	p. 246
Partitioning into Sets of Bounded Cardinality	p. 258
Two Edge Modification Problems without Polynomial Kernels	p. 264
On the Directed Degree-Preserving Spanning Tree Problem	p. 276
Even Faster Algorithms for Set Splitting!	p. 288
Stable Assignment with Couples: Parameterized Complexity and Local Search	p. 300
Improved Parameterized Algorithms for the Kemeny Aggregation Problem	p. 312
Computing Pathwidth Faster Than 2n	p. 324
Author Index	p. 337
Table of Contents provided by Ingram. All Rights Reserved.