On Finding Directed Trees with Many Leaves

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The 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.
Submitted to ESA 09, 13 pages, 1 figure

Keywords

Discrete Mathematics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/227554

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0904.2658
 http://arxiv.org/abs/0904.2658

Collections

arXiv