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.1007/978-3-642-02882-3_5

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: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

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.704 ^k ) 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. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).

Original language	English
Title of host publication	Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings
Pages	37-46
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-02882-3_5
Publication status	Published - 2009
Externally published	Yes
Event	15th Annual International Conference on Computing and Combinatorics, COCOON 2009 - Niagara Falls, NY, United States Duration: 13 Jul 2009 → 15 Jul 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5609 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th Annual International Conference on Computing and Combinatorics, COCOON 2009
Country/Territory	United States
City	Niagara Falls, NY
Period	13/07/09 → 15/07/09

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-02882-3_5

Cite this

Cohen, N., Fomin, F. V., Gutin, G., Kim, E. J., Saurabh, S., & Yeo, A. (2009). Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. In Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings (pp. 37-46). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5609 LNCS). https://doi.org/10.1007/978-3-642-02882-3_5

Cohen, Nathann ; Fomin, Fedor V. ; Gutin, Gregory et al. / Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings. 2009. pp. 37-46 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c82f4e85df0f499f86f51d0d86edae3b,

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 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.704 k ) 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. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).",

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

year = "2009",

doi = "10.1007/978-3-642-02882-3\_5",

language = "English",

isbn = "3642028810",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "37--46",

booktitle = "Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings",

note = "15th Annual International Conference on Computing and Combinatorics, COCOON 2009 ; Conference date: 13-07-2009 Through 15-07-2009",

}

Cohen, N, Fomin, FV, Gutin, G, Kim, EJ, Saurabh, S & Yeo, A 2009, Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. in Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5609 LNCS, pp. 37-46, 15th Annual International Conference on Computing and Combinatorics, COCOON 2009, Niagara Falls, NY, United States, 13/07/09. https://doi.org/10.1007/978-3-642-02882-3_5

Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. / Cohen, Nathann; Fomin, Fedor V.; Gutin, Gregory et al.
Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings. 2009. p. 37-46 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5609 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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 - 2009

Y1 - 2009

N2 - 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.704 k ) 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. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).

AB - 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.704 k ) 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. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).

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

U2 - 10.1007/978-3-642-02882-3_5

DO - 10.1007/978-3-642-02882-3_5

M3 - Conference contribution

AN - SCOPUS:75649137550

SN - 3642028810

SN - 9783642028816

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 37

EP - 46

BT - Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings

T2 - 15th Annual International Conference on Computing and Combinatorics, COCOON 2009

Y2 - 13 July 2009 through 15 July 2009

ER -

Cohen N, Fomin FV, Gutin G, Kim EJ, Saurabh S, Yeo A. Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. In Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings. 2009. p. 37-46. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-02882-3_5

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this