Finding four independent trees

被引：73

作者：

Curran, S ^{[1
]}

Lee, O

Yu, XX

机构：

[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

[2] Univ Estadual Campinas, Inst Computacao, BR-13083971 Campinas, SP, Brazil

[3] Nankai Univ, LPMC, Ctr Combinator, Tianjin 300071, Peoples R China

来源：

SIAM JOURNAL ON COMPUTING | 2006年 / 35卷 / 05期

关键词：

connectivity; chain decomposition; numbering; independent trees; algorithm;

D O I：

10.1137/S0097539703436734

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Motivated by a multitree approach to the design of reliable communication protocols, Itai and Rodeh gave a linear time algorithm for finding two independent spanning trees in a 2-connected graph. Cheriyan and Maheshwari gave an O(vertical bar V vertical bar(2)) algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an O(vertical bar V vertical bar(3)) algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs.

引用

页码：1023 / 1058

页数：36

共 14 条

[1] FINDING NONSEPARATING INDUCED CYCLES AND INDEPENDENT SPANNING-TREES IN 3-CONNECTED GRAPHS [J].

CHERIYAN, J ;

MAHESHWARI, SN .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1988, 9 (04) :507-537

[2]

Cormen T. H., 2001, Introduction to Algorithms, V2nd

[3]

CURRAN S, 2003, INDEPENDENT TREES 4

[4] CHAIN DECOMPOSITIONS OF 4-CONNECTED GRAPHS [J].

Curran, Sean ;

Lee, Orlando ;

Yu, Xingxing .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 19 (04) :848-880

[5]

Dolev Danny, 1984, P 16 ANN ACM S THEOR, P526

[6]

Frank A., 1995, HDB COMBINATORICS, V1, P111

[7] EFFICIENT PLANARITY TESTING [J].

HOPCROFT, J ;

TARJAN, R .

JOURNAL OF THE ACM, 1974, 21 (04) :549-568

[8] INDEPENDENT TREES IN GRAPHS [J].

HUCK, A .

GRAPHS AND COMBINATORICS, 1994, 10 (01) :29-45

[9]

ITAI A, 1984, P 25 ANN IEEE S FDN, P137

[10]

Miura K., 1999, International Journal of Foundations of Computer Science, V10, P195, DOI 10.1142/S0129054199000149

← 1 2 →