Spanning directed trees with many leaves

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh

Research output: Contribution to journalArticle

20 Scopus citations

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 obtain two combinatorial results on the number of leaves in out-branchings. We show that (1) every strongly connected n-vertex digraph D with minimum in-degree at least 3 has an outbranching with at least (n/4)1/3 - 1 leaves; (2) if a strongly connected digraph D does not contain an out-branching with k leaves, then the pathwidth of its underlying graph UG(D) is O(k log k), and if the digraph is acyclic with a single vertex of in-degree zero, then the pathwidth is at most 4k. The last result implies that it can be decided in time 2O(k log2 k) · nO(1) whether a strongly connected digraph on n vertices has an out-branching with at least k leaves. On acyclic digraphs the running time of our algorithm is 2O(k log k) · nO(1).

Original languageEnglish (US)
Pages (from-to)466-476
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Volume23
Issue number1
DOIs
StatePublished - Dec 1 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Directed graphs
  • Fixed parameter tractability
  • Maximum leaf
  • Out-branching
  • Rooted tree

Fingerprint Dive into the research topics of 'Spanning directed trees with many leaves'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Fomin, F. V., Gutin, G., Krivelevich, M., & Saurabh, S. (2008). Spanning directed trees with many leaves. SIAM Journal on Discrete Mathematics, 23(1), 466-476. https://doi.org/10.1137/070710494