Parameterized and Exact Computation: 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers

✍ Scribed by Noga Alon, Shai Gutner (auth.), Jianer Chen, Fedor V. Fomin (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2009
• Tongue: English
• Leaves: 345
• Series: Lecture Notes in Computer Science 5917 : Theoretical Computer Science and General Issues
• Edition: 1
• Category: Library

✦ Synopsis

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

Front Matter....Pages -
Balanced Hashing, Color Coding and Approximate Counting....Pages 1-16
Kernelization: New Upper and Lower Bound Techniques....Pages 17-37
A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams....Pages 38-49
Planar Capacitated Dominating Set Is W [1]-Hard....Pages 50-60
Boolean-Width of Graphs....Pages 61-74
The Complexity of Satisfiability of Small Depth Circuits....Pages 75-85
On Finding Directed Trees with Many Leaves....Pages 86-97
Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms....Pages 98-109
Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover....Pages 110-121
What Makes Equitable Connected Partition Easy....Pages 122-133
Improved Induced Matchings in Sparse Graphs....Pages 134-148
Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs....Pages 149-160
An Exact Algorithm for the Maximum Leaf Spanning Tree Problem....Pages 161-172
An Exponential Time 2-Approximation Algorithm for Bandwidth....Pages 173-184
On Digraph Width Measures in Parameterized Algorithmics....Pages 185-197
The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension....Pages 198-209
Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms....Pages 210-221
Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs....Pages 222-233
A Probabilistic Approach to Problems Parameterized above or below Tight Bounds....Pages 234-245
Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor....Pages 246-257
Partitioning into Sets of Bounded Cardinality....Pages 258-263
Two Edge Modification Problems without Polynomial Kernels....Pages 264-275
On the Directed Degree-Preserving Spanning Tree Problem....Pages 276-287
Even Faster Algorithm for Set Splitting !....Pages 288-299
Stable Assignment with Couples: Parameterized Complexity and Local Search....Pages 300-311
Improved Parameterized Algorithms for the Kemeny Aggregation Problem....Pages 312-323
Computing Pathwidth Faster Than 2 n ....Pages 324-335
Back Matter....Pages -

✦ Subjects

Algorithm Analysis and Problem Complexity; Algorithms; Discrete Mathematics in Computer Science; Theory of Computation; Symbolic and Algebraic Manipulation; Logics and Meanings of Programs