Better Algorithms and Bounds for Directed Maximum Leaf Problems
| dc.creator | Alon, Noga | |
| dc.creator | Fomin, Fedor V. | |
| dc.creator | Gutin, Gregory | |
| dc.creator | Krivelevich, Michael | |
| dc.creator | Saurabh, Saket | |
| dc.date | 2007-07-07 | |
| dc.date.accessioned | 2026-07-07T08:14:32Z | |
| dc.date.available | 2026-07-07T08:14:32Z | |
| dc.description | 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 this paper, we improve known parameterized algorithms and combinatorial bounds on the number of leaves in out-branchings. We show that \begin{itemize} \item every strongly connected digraph $D$ of order $n$ with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; \item if a strongly connected digraph $D$ does not contain an out-branching with $k$ leaves, then the pathwidth of its underlying graph is $O(k\log k)$; \item it can be decided in time $2^{O(k\log^2 k)}\cdot n^{O(1)}$ whether a strongly connected digraph on $n$ vertices has an out-branching with at least $k$ leaves. \end{itemize} All improvements use properties of extremal structures obtained after applying local search and of some out-branching decompositions. | |
| dc.identifier | https://arxiv.org/abs/0707.1095 | |
| dc.identifier | http://arxiv.org/abs/0707.1095 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/133157 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.title | Better Algorithms and Bounds for Directed Maximum Leaf Problems | |
| dc.type | text |