On Finding Directed Trees with Many Leaves

Simple item page
dc.creatorDaligault, Jean
dc.creatorThomasse, Stephan
dc.date2009-04-17
dc.date.accessioned2026-07-07T13:05:39Z
dc.date.available2026-07-07T13:05:39Z
dc.descriptionThe Rooted Maximum Leaf Outbranching 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 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. We also show that Rooted Maximum Leaf Outbranching admits a quadratic kernel, improving over the cubic kernel given by Fernau et al.
dc.descriptionSubmitted to ESA 09, 13 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/0904.2658
dc.identifierhttp://arxiv.org/abs/0904.2658
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/227554
dc.subjectDiscrete Mathematics
dc.titleOn Finding Directed Trees with Many Leaves
dc.typetext

Files

Collections

arXiv