121 citations · 360 across the 111 of their papers we have counts for
Showing 2007Show all
2 papers · 1 filter
cs.DS2007★ 4 cited
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…
cs.DS2007
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…