Algorithm for Finding $k$-Vertex Out-trees and its Application to $k$-Internal Out-branching Problem
| dc.creator | Cohen, Nathann | |
| dc.creator | Fomin, Fedor V. | |
| dc.creator | Gutin, Gregory | |
| dc.creator | Kim, Eun Jung | |
| dc.creator | Saurabh, Saket | |
| dc.creator | Yeo, Anders | |
| dc.date | 2009-03-05 | |
| dc.date.accessioned | 2026-07-07T12:49:17Z | |
| dc.date.available | 2026-07-07T12:49:17Z | |
| dc.description | 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). | |
| dc.identifier | https://arxiv.org/abs/0903.0938 | |
| dc.identifier | http://arxiv.org/abs/0903.0938 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/222350 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Algorithm for Finding $k$-Vertex Out-trees and its Application to $k$-Internal Out-branching Problem | |
| dc.type | text |