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}.
Type de document :
Communication dans un congrès
IWPEC'09: International Workshop on Parameterized and Exact Computation, Copenhagen, Denmark. Elsevier, pp.86-97, 2009, LNCS. 〈10.1007/978-3-642-11269-0_7〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432919
Contributeur : Jean Daligault <>
Soumis le : mardi 17 novembre 2009 - 16:08:06
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : jeudi 17 juin 2010 - 20:44:10

Fichier

maxleaf.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

217

Téléchargements de fichiers

63