Spanning directed trees with many leaves

Details Spanning directed trees with many leaves Spanning directed trees with many leaves

2008-03-05

arxiv.org/abs/0803.0701v1

Computer Science

Data Structures and Algorithms

Scientific paper

The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that - every strongly connected $n$-vertex digraph $D$ with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; - if a strongly connected digraph $D$ does not contain an out-branching with $k$ leaves, then the pathwidth of its underlying graph UG($D$) is $O(k\log k)$. Moreover, if the digraph is acyclic, the pathwidth is at most $4k$. The last result implies that it can be decided in time $2^{O(k\log^2 k)}\cdot n^{O(1)}$ whether a strongly connected digraph on $n$ vertices has an out-branching with at least $k$ leaves. On acyclic digraphs the running time of our algorithm is $2^{O(k\log k)}\cdot n^{O(1)}$.

Affiliated with

Also associated with

No associations

Rating

Spanning 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 Spanning directed trees with many leaves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning directed trees with many leaves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-161556