Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems

Paul Bonsma, Frederic Dorn

An out-tree $T$ of a directed graph $D$ is a rooted tree subgraph with all arcs directed outwards from the root. An out-branching is a spanning out-tree. By $l(D)$ and $l_s(D)$ we…