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

Nathann Cohen; Fedor V. Fomin; Gregory Gutin; Eun Jung Kim; Saket Saurabh; Anders Yeo

doi:10.1016/j.jcss.2010.01.001

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

Nathann Cohen
, Fedor V. Fomin
, Gregory Gutin
, Eun Jung Kim
, Saket Saurabh
, Anders Yeo

Research output: Contribution to journal › Article › peer-review

35 Citations (Scopus)

Abstract

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. AAIM'08) [9].

Original language	English
Pages (from-to)	650-662
Number of pages	13
Journal	Journal of Computer and System Sciences
Volume	76
Issue number	7
DOIs	https://doi.org/10.1016/j.jcss.2010.01.001
Publication status	Published - 2010
Externally published	Yes

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.jcss.2010.01.001

Cite this

@article{7b23cf361f684260b40b0da5acc14b39,

title = "Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem",

abstract = "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.704k) and O*(6.14k), respectively. We apply the deterministic algorithm to obtain a deterministic algorithm of runtime O*(ck), 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) [9].",

keywords = "Divide-and-conquer, Internal vertices, Out-branching, Out-tree",

author = "Nathann Cohen and Fomin, \{Fedor V.\} and Gregory Gutin and Kim, \{Eun Jung\} and Saket Saurabh and Anders Yeo",

year = "2010",

doi = "10.1016/j.jcss.2010.01.001",

language = "English",

volume = "76",

pages = "650--662",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "7",

}

TY - JOUR

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

AU - Cohen, Nathann

AU - Fomin, Fedor V.

AU - Gutin, Gregory

AU - Kim, Eun Jung

AU - Saurabh, Saket

AU - Yeo, Anders

PY - 2010

Y1 - 2010

N2 - 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.704k) and O*(6.14k), respectively. We apply the deterministic algorithm to obtain a deterministic algorithm of runtime O*(ck), 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) [9].

AB - 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.704k) and O*(6.14k), respectively. We apply the deterministic algorithm to obtain a deterministic algorithm of runtime O*(ck), 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) [9].

KW - Divide-and-conquer

KW - Internal vertices

KW - Out-branching

KW - Out-tree

UR - https://www.scopus.com/pages/publications/77955418718

U2 - 10.1016/j.jcss.2010.01.001

DO - 10.1016/j.jcss.2010.01.001

M3 - Article

AN - SCOPUS:77955418718

SN - 0022-0000

VL - 76

SP - 650

EP - 662

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 7

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this