# On Finding Directed Trees with Many Leaves

2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The Rooted Maximum Leaf problem consists in finding a spanning directed tree rooted at some prescribed vertex of a digraph with the maximum number of leaves. Its parameterized version asks if there exists such a tree with at least $k$ leaves. We use the notion of $s-t$ numbering studied in \cite{stnum, stnumdir,LLWemb} to exhibit combinatorial bounds on the existence of spanning directed trees with many leaves. These combinatorial bounds allow us to produce a constant factor approximation algorithm for finding directed trees with many leaves, whereas the best known approximation algorithm has a $\sqrt{OPT}$-factor \cite{DrescherMaxLeaf}. We also show that Rooted Maximum Leaf admits an edge-quadratic kernel, improving over the vertex-cubic kernel given by Fernau et al \cite{FernauMaxLeaf}.
Document type :
Conference papers

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432919
Contributor : Jean Daligault <>
Submitted on : Tuesday, November 17, 2009 - 4:08:06 PM
Last modification on : Thursday, September 19, 2019 - 2:00:12 PM
Long-term archiving on: : Thursday, June 17, 2010 - 8:44:10 PM

### File

maxleaf.pdf
Files produced by the author(s)

### Citation

Jean Daligault, Stéphan Thomassé. On Finding Directed Trees with Many Leaves. IWPEC: International Workshop on Parameterized and Exact Computation, Sep 2009, Copenhagen, Denmark. pp.86-97, ⟨10.1007/978-3-642-11269-0_7⟩. ⟨lirmm-00432919⟩

Record views