@inproceedings{01d215969bd34cf0824207c28700dc00,
title = "Better algorithms and bounds for directed maximum leaf problems",
abstract = "The 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 - every strongly connected digraph D of order n with minimum indegree at least 3 has an out-branching with at least (n/4)1/3 - 1 leaves; - 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); - it can be decided in time 2O(k log2k)·nO(1) whether a strongly connected digraph on n vertices has an out-branching with at least k leaves. All improvements use properties of extremal structures obtained after applying local search and properties of some out-branching decompositions.",
author = "Noga Alon and Fomin, {Fedor V.} and Gregory Gutin and Michael Krivelevich and Saket Saurabh",
year = "2007",
doi = "10.1007/978-3-540-77050-3_26",
language = "English (US)",
isbn = "9783540770497",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "316--327",
booktitle = "FSTTCS 2007",
address = "Germany",
note = "27th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007 ; Conference date: 12-12-2007 Through 14-12-2007",
}