29 citations · 98 across the 20 of their papers we have counts for
6 papers · 1 filter
Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
Julien Baste, Michael R. Fellows, Lars Jaffke +4
When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instanc…
What is known about Vertex Cover Kernelization?
Michael R. Fellows, Lars Jaffke, Aliz Izabella Király +2
We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkovič on the occasion of his 60th birthday. The Vertex Cover problem is…
Simultaneously Satisfying Linear Equations Over : MaxLin2 and Max--Lin2 Parameterized Above Average
R. Crowston, M. Fellows, G. Gutin +4
In the parameterized problem \textsc{MaxLin2-AA}[], we are given a system with variables consisting of equations of the form , where $x_i,b…
Parameterizing by the Number of Numbers
Michael R. Fellows, Serge Gaspers, Frances A. Rosamond
The usefulness of parameterized algorithmics has often depended on what Niedermeier has called, "the art of problem parameterization". In this paper we introduce and explore a nove…
Parameterized Low-distortion Embeddings - Graph metrics into lines and trees
Michael Fellows, Fedor Fomin, Daniel Lokshtanov +3
We revisit the issue of low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity persp…
Polynomial Time Data Reduction for Dominating Set
Jochen Alber, Michael R. Fellows, Rolf Niedermeier
Dealing with the NP-complete Dominating Set problem on undirected graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side…