2009/04/17 by Jean Daligault, Daligault, Jean, Stéphan Thomassé +2
Computer Science · #Advanced Graph Theory Research #Data Management and Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.DM
paper · pdf · doi:10.48550/arxiv.0904.2658
Submitted to ESA 09, 13 pages, 1 figure
arxiv created 2009/04/17 · openalex publication_date 2009/04/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 √(OPT)-factor. We also show that Rooted Maximum Leaf Outbranching admits a quadratic kernel, improving over the cubic kernel given by Fernau et al.