On Finding Directed Trees with Many Leaves - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2009

On Finding Directed Trees with Many Leaves

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}.
Fichier principal
Vignette du fichier
maxleaf.pdf (206.59 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00432919 , version 1 (17-11-2009)

Identifiers

Cite

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⟩
164 View
117 Download

Altmetric

Share

More