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

被引：29

作者：

Cohen, Nathann ^{[2
]}

Fomin, Fedor V. ^{[3
]}

Gutin, Gregory ^{[1
]}

Kim, Eun Jung ^{[1
]}

Saurabh, Saket ^{[3
]}

Yeo, Anders ^{[1
]}

机构：

[1] Univ London, Dept Comp Sci, Egham TW20 0EX, Surrey, England

[2] INRIA Projet MASCOTTE, F-06902 Sophia Antipolis, France

[3] Univ Bergen, Dept Informat, N-5020 Bergen, Norway

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2010年 / 76卷 / 07期

关键词：

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

D O I：

10.1016/j.jcss.2010.01.001

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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]. (C) 2010 Elsevier Inc. All rights reserved.

引用

页码：650 / 662

页数：13

共 16 条

[1] COLOR-CODING [J].

ALON, N ;

YUSTER, R ;

ZWICK, U .

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (04) :844-856

[2]

Bang-Jensen J, 2009, SPRINGER MONOGR MATH, P1, DOI 10.1007/978-1-84800-998-1_1

[3] CONSTANT TIME GENERATION OF ROOTED TREES [J].

BEYER, T ;

HEDETNIEMI, SM .

SIAM JOURNAL ON COMPUTING, 1980, 9 (04) :706-712

[4] RANDOMIZED DIVIDE-AND-CONQUER: IMPROVED PATH, MATCHING, AND PACKING ALGORITHMS [J].

Chen, Jianer ;

Kneis, Joachim ;

Lu, Songjian ;

Moelle, Daniel ;

Richter, Stefan ;

Rossmanith, Peter ;

Sze, Sing-Hoi ;

Zhang, Fenghui .

SIAM JOURNAL ON COMPUTING, 2009, 38 (06) :2526-2547

[5]

Chung F.R. K., 1990, Algorithms Comb., V9, P17

[6]

Cohen N, 2009, LECT NOTES COMPUT SC, V5609, P37, DOI 10.1007/978-3-642-02882-3_5

[7]

DEMERS A, 2000, Patent No. 6105018

[8] STORING A SPARSE TABLE WITH O(1) WORST CASE ACCESS TIME [J].

FREDMAN, ML ;

KOMLOS, J ;

SZEMEREDI, E .

JOURNAL OF THE ACM, 1984, 31 (03) :538-544

[9]

Gutin G, 2008, LECT NOTES COMPUT SC, V5034, P235, DOI 10.1007/978-3-540-68880-8_23

[10]

Koutis I, 2008, LECT NOTES COMPUT SC, V5125, P575, DOI 10.1007/978-3-540-70575-8_47

← 1 2 →