Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem

作者：Cohen Nathann; Fomin Fedor V; Gutin Gregory^*; Kim Eun Jung; Saurabh Saket; Yeo Anders

来源：Journal of Computer and System Sciences, 2010, 76(7): 650-662.

DOI：10.1016/j.jcss.2010.01.001

• Out-tree
• Out-branching
• Internal vertices
• Divide-and-conquer

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 running time O*(5.704(k)) and O*(6.14(k)), 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. AA1M'08) [9].

• 出版日期2010-11
• 单位INRIA