Preprocessing, or data reduction, is a standard technique for simplifying and speeding up
computation. Written by a team of experts in the field, this book introduces a rapidly …

Parameterized complexity/multivariate complexity algorithmics is an exciting field of modern
algorithm design and analysis, with a broad range of theoretical and practical aspects that …

Classical complexity theory analyzes and classifies problems by the amount of a resource,
usually time or space, that is required by algorithms solving them. It was a fundamental idea …

This paper presents an O (1.2738 k+ kn)-time polynomial-space algorithm for Vertex Cover
improving the previous O (1.286 k+ kn)-time polynomial-space upper bound by Chen, Kanj …

Let F be a finite set of graphs. In the F-DELETION problem, we are given an n-vertex graph
G and an integer k as input, and asked whether at most k vertices can be deleted from G …

The paper studies crown reductions for the Minimum Weighted Vertex Cover problem
introduced recently in the unweighted case by Fellows et al.[Blow-Ups, Win/Win's and crown …

Parameterized Algorithmics: A Graph-Theoretic Approach Page 1 Parameterized Algorithmics:
A Graph-Theoretic Approach Henning Fernau Universität Tübingen, WSI für Informatik, Sand …

Abstract In the Cluster Editing problem, a graph is to be changed to a disjoint union of
cliques by at most k operations of edge insertion or edge deletion. Improving on the best …

We describe an algorithm for the Feedback Vertex Set problem on undirected graphs,
parameterized by the size k of the feedback vertex set, that runs in time O (ckn 3) where c …

FPT is P-Time Extremal Structure I Page 1 FPT is P-Time Extremal Structure I VLADIMIR
ESTIVILL-CASTRO 1 , MICHAEL FELLOWS 2 , MICHAEL LANGSTON 3 , FRANCES …