7 citations · 16 across the 6 of their papers we have counts for
7 papers
Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves
Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov +3
The {\sc -Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) with at least leaves in a given digraph. The problem has recently re…
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…
Spanning directed trees with many leaves
N Alon, F. V. Fomin, G. Gutin +2
The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In th…
Parameterized Algorithms for Partial Cover Problems
Omid Amini, Fedor V. Fomin, Saket Saurabh
Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite…
Better Algorithms and Bounds for Directed Maximum Leaf Problems
Noga Alon, Fedor V. Fomin, Gregory Gutin +2
The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In th…
Parameterized Algorithms for Directed Maximum Leaf Problems
Noga Alon, Fedor Fomin, Gregory Gutin +2
We prove that finding a rooted subtree with at least leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with m…