On Finding Directed Trees with Many Leaves

Details On Finding Directed Trees with Many Leaves On Finding Directed Trees with Many Leaves

2009-04-17

arxiv.org/abs/0904.2658v1

Computer Science

Discrete Mathematics

Submitted to ESA 09, 13 pages, 1 figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On Finding Directed Trees with Many Leaves does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Finding Directed Trees with Many Leaves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Finding Directed Trees with Many Leaves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-141045