Parameterized Algorithms for Directed Maximum Leaf Problems
| dc.creator | Alon, Noga | |
| dc.creator | Fomin, Fedor | |
| dc.creator | Gutin, Gregory | |
| dc.creator | Krivelevich, Michael | |
| dc.creator | Saurabh, Saket | |
| dc.date | 2007-02-08 | |
| dc.date.accessioned | 2026-07-07T07:45:31Z | |
| dc.date.available | 2026-07-07T07:45:31Z | |
| dc.description | We prove that finding a rooted subtree with at least $k$ leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in digraphs from a wide family $\cal L$ that includes all strong and acyclic digraphs. This settles completely an open question of Fellows and solves another one for digraphs in $\cal L$. Our algorithms are based on the following combinatorial result which can be viewed as a generalization of many results for a `spanning tree with many leaves' in the undirected case, and which is interesting on its own: If a digraph $D\in \cal L$ of order $n$ with minimum in-degree at least 3 contains a rooted spanning tree, then $D$ contains one with at least $(n/2)^{1/5}-1$ leaves. | |
| dc.identifier | https://arxiv.org/abs/cs/0702049 | |
| dc.identifier | http://arxiv.org/abs/cs/0702049 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/123553 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.title | Parameterized Algorithms for Directed Maximum Leaf Problems | |
| dc.type | text |