Completely independent spanning trees in torus networks

被引：53

作者：

Hasunuma, Toru ^{[1
]}

Morisaka, Chie ^{[1
]}

机构：

[1] Univ Tokushima, Dept Math & Nat Sci, Tokushima 7708502, Japan

来源：

NETWORKS | 2012年 / 60卷 / 01期

关键词：

completely independent spanning trees; edge-disjoint spanning trees; torus network; cartesian product; interconnection network; fault-tolerance; PLANAR GRAPHS; SMALL DEPTHS; CONSTRUCTION; HYPERCUBES; CYCLES;

D O I：

10.1002/net.20460

中图分类号：

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

学科分类号：

0812 ;

摘要：

Let T1, T2, ..., Tk be spanning trees in a graph G. If for any two vertices u, v in G, the paths from u to v in T1, T2, ..., Tk are pairwise internally disjoint, then T1, T2, ..., Tk are completely independent spanning trees in G. Completely independent spanning trees can be applied to fault-tolerant communication problems in interconnection networks. In this article, we show that there are two completely independent spanning trees in any torus network. Besides, we generalize the result for the Cartesian product. In particular, we show that there are two completely independent spanning trees in the Cartesian product of any 2-connected graphs. (c) 2011 Wiley Periodicals, Inc. NETWORKS, 2012

引用

页码：59 / 69

页数：11

共 28 条

[1] On edge-disjoint spanning trees in hypercubes [J].

Barden, B ;

Libeskind-Hadas, R ;

Davis, J ;

Williams, W .

INFORMATION PROCESSING LETTERS, 1999, 70 (01) :13-16

[2] Vertex disjoint routings of cycles over Tori [J].

Bermond, Jean-Claude ;

Yu, Min-Li .

NETWORKS, 2007, 49 (03) :217-225

[3] 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

[4] Finding four independent trees [J].

Curran, S ;

Lee, O ;

Yu, XX .

SIAM JOURNAL ON COMPUTING, 2006, 35 (05) :1023-1058

[5] Edge-disjoint spanning trees on the star network with applications to fault tolerance [J].

Fragopoulou, P ;

Akl, SG .

IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (02) :174-185

[6] Disjoint rooted spanning trees with small depths in deBruijn and Kautz graphs [J].

Ge, ZY ;

Hakimi, SL .

SIAM JOURNAL ON COMPUTING, 1997, 26 (01) :79-92

[7]

Hasunuma T, 2002, LECT NOTES COMPUT SC, V2573, P235

[8] Independent spanning trees with small depths in iterated line digraphs [J].

Hasunuma, T ;

Nagamochi, H .

DISCRETE APPLIED MATHEMATICS, 2001, 110 (2-3) :189-211

[9] Completely independent spanning trees in the underlying graph of a line digraph [J].

Hasunuma, T .

DISCRETE MATHEMATICS, 2001, 234 (1-3) :149-157

[10]

Huck A, 1999, GRAPH COMBINATOR, V15, P29

← 1 2 3 →