Computer Science – Data Structures and Algorithms
Scientific paper
2009-03-05
Computer Science
Data Structures and Algorithms
Scientific paper
An out-tree $T$ is an oriented tree with only one vertex of in-degree zero. A vertex $x$ of $T$ is internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a given out-tree with $k$ vertices. The algorithms are of runtime $O^*(5.704^k)$ and $O^*(5.704^{k(1+o(1))})$, respectively. We apply the deterministic algorithm to obtain a deterministic algorithm of runtime $O^*(c^k)$, where $c$ is a constant, for deciding whether an input digraph contains a spanning out-tree with at least $k$ internal vertices. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).
Cohen Nathann
Fomin Fedor V.
Gutin Gregory
Kim Eun Jung
Saurabh Saket
No associations
LandOfFree
Algorithm for Finding $k$-Vertex Out-trees and its Application to $k$-Internal Out-branching Problem 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 Algorithm for Finding $k$-Vertex Out-trees and its Application to $k$-Internal Out-branching Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithm for Finding $k$-Vertex Out-trees and its Application to $k$-Internal Out-branching Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-115079