Cohen, Nathann ; Fomin, Fedor V. ; Gutin, Gregory ; Kim, Eun Jung ; Saurabh, Saket ; Yeo, Anders (2010) Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem Journal of Computer and System Sciences, 76 (7). pp. 650-662. ISSN 0022-0000
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.jcss.2010.01.001
Related URL: http://dx.doi.org/10.1016/j.jcss.2010.01.001
Abstract
An out-tree T is an oriented tree with exactly one vertex of in-degree zero and a vertex x of T is called internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a subgraph isomorphic to a given out-tree with k vertices. Both algorithms run in O*(5.704k ) time. We apply the deterministic algorithm to obtain an 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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 123475 |
| Deposited On: | 20 Sep 2021 10:48 |
| Last Modified: | 20 Sep 2021 10:48 |
Repository Staff Only: item control page
