期刊
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
卷 17, 期 3, 页码 227-240出版社
IEEE COMPUTER SOC
DOI: 10.1109/TPDS.2006.37
关键词
fault tolerance; network topology; graph theory; fault-Hamiltonicity; embedding; strong Hamiltonicity; recursive circulants; restricted HL-graphs
A many-to-many-to-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. We deal with the graph G(0) circle plus G(1) obtained from connecting two graphs G(0) and G(1) with n vertices each by n pairwise nonadjacent edges joining vertices in G(0) and vertices in G(1). Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G(0) circle plus G(1) connecting two lower dimensional networks G(0) and G(1). In the presence of faulty vertices and/or edges, we investigate many-to-many disjoint path coverability of G(0) circle plus G(1) and (G(0) circle plus G(1)) circle plus (G(2) circle plus G(3)), provided some conditions on the Hamiltonicity and disjoint path coverability of each graph G(i) are satisfied, 0 <= i <= 3. We apply our main results to recursive circulant G(2(m),4) and a subclass of hypercube-like interconnection networks, called restricted HL-graphs. The subclass includes twisted cubes, crossed cubes, multiply twisted cubes, Mobius cubes, Mcubes, and generalized twisted cubes. We show that all these networks of degree m with f or less faulty elements have a many-to-many k-DPC joining any k distinct source-sink pairs for any k; >= 1 and f >= 0 such that f + 2k: <= m - 1.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据