首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
The hypercube has been one of the most popular interconnection networks for parallel computer/communication systems. In this paper, we assume that each node is incident with at least two fault-free links. Under this assumption, we show that every fault-free edge lies on a fault-free cycle of every even length from 6 to 2n inclusive, even if it has up to 2n − 5 link faults. The result is optimal with respect to the number of link faults tolerated.  相似文献   

2.
The crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, assuming that each node is incident with at least two fault-free links, we show that an n-dimensional crossed cube contains a fault-free Hamiltonian cycle, even if there are up to 2n − 5 link faults. The result is optimal with respect to the number of link faults tolerated. We also verify that the assumption is practically meaningful by evaluating its occurrence probability, which is very close to 1.  相似文献   

3.
The dual-cube is an interconnection network for linking a large number of nodes with a low node degree. It uses low-dimensional hypercubes as building blocks and keeps the main desired properties of the hypercube. A dual-cube DC(n) has n + 1 links per node where n is the degree of a cluster (n-cube), and one more link is used for connecting to a node in another cluster. In this paper, assuming each node is incident with at least two fault-free links, we show a dual-cube DC(n) contains a fault-free Hamiltonian cycle, even if it has up to 2n − 3 link faults. The result is optimal with respect to the number of tolerant edge faults.  相似文献   

4.
The hypercube is one of the most versatile and efficient interconnection networks (networks for short) so far discovered for parallel computation. Let f denote the number of faulty vertices in an n-cube. This study demonstrates that when f ? n − 2, the n-cube contains a fault-free path with length at least 2n − 2f − 1 (or 2n − 2f − 2) between two arbitrary vertices of odd (or even) distance. Since an n-cube is a bipartite graph with two partite sets of equal size, the path is longest in the worst-case. Furthermore, since the connectivity of an n-cube is n, the n-cube cannot tolerate n − 1 faulty vertices. Hence, our result is optimal.  相似文献   

5.
Che-Nan Kuo 《Information Sciences》2010,180(15):2904-3675
A graph is said to be pancyclic if it contains cycles of every length from its girth to its order inclusive; and a bipartite graph is said to be bipancyclic if it contains cycles of every even length from its girth to its order. The pancyclicity or the bipancyclicity of a given network is an important factor in determining whether the network’s topology can simulate rings of various lengths. An n-dimensional folded hypercube FQn is an attractive variant of an n-dimensional hypercube Qn that is obtained by establishing some extra edges between the vertices of Qn. FQn for any odd n is known to be bipartite. In this paper, we explore the pancyclicity and bipancyclicity of FQn. For any FQn (n ? 2) with at most 2n − 3 faulty edges, where each vertex is incident to at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2n; and when n ? 2 is even, we prove there also exists a fault-free cycle of every odd length from n + 1 to 2n − 1. The result is optimal with respect to the number of faulty edges tolerated.  相似文献   

6.
The conditional fault model imposes a constraint on the fault distribution. For example, the most commonly imposed constraint for edge faults is that each vertex is incident with two or more non-faulty edges. In this paper, subject to this constraint, we show that an nn-dimensional pancake graph can tolerate up to 2n−72n7 edge faults, while retaining a fault-free Hamiltonian cycle, where n≥4n4. Previously, at most n−3n3 edge faults can be tolerated for the same problem, if the edge faults may occur anywhere without imposing any constraint.  相似文献   

7.
The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(nk), that make every (n − k)-dimensional substar Snk faulty in an n-dimensional star network Sn, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n3) which is an improvement over the straightforward upper bound of O(n4) derived in this paper.  相似文献   

8.
The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with fv faulty nodes and fe faulty edges lies in a fault-free cycle of every even length from 4 to kn − 2fv (resp. kn − fv) if k ? 4 is even (resp. k ? 3 is odd) and fv + fe ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.  相似文献   

9.
Hamiltonian laceability of bubble-sort graphs with edge faults   总被引:1,自引:0,他引:1  
It is known that the n-dimensional bubble-sort graph Bn is bipartite, (n − 1)-regular, and has n! vertices. We first show that, for any vertex v, Bn − v has a hamiltonian path between any two vertices in the same partite set without v. Let F be a subset of edges of Bn. We next show that Bn − F has a hamiltonian path between any two vertices of different partite sets if ∣F∣ is at most n − 3. Then we also prove that Bn − F has a path of length n! − 2 between any pair of vertices in the same partite set.  相似文献   

10.
As a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis of multicomputers, the t/k diagnosis strategy can significantly improve the self-diagnosing capability of a system at the expense of no more than k fault-free processors (nodes) being mistakenly diagnosed as faulty. In the case k ? 2, to our knowledge, there is no known t/k diagnosis algorithm for general diagnosable system or for any specific system. Hypercube is a popular topology for interconnecting processors of multicomputers. It is known that an n-dimensional cube is (4n − 9)/3-diagnosable. This paper addresses the (4n − 9)/3 diagnosis of n-dimensional cube. By exploring the relationship between a largest connected component of the 0-test subgraph of a faulty hypercube and the distribution of the faulty nodes over the network, the fault diagnosis of an n-dimensional cube can be reduced to those of two constituent (n − 1)-dimensional cubes. On this basis, a diagnosis algorithm is presented. Given that there are no more than 4n − 9 faulty nodes, this algorithm can isolate all faulty nodes to within a set in which at most three nodes are fault-free. The proposed algorithm can operate in O(N log2 N) time, where N = 2n is the total number of nodes of the hypercube. The work of this paper provides insight into developing efficient t/k diagnosis algorithms for larger k value and for other types of interconnection networks.  相似文献   

11.
Edge-pancyclicity and path-embeddability of bijective connection graphs   总被引:1,自引:0,他引:1  
An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2n nodes and n2n−1 edges. The n-dimensional hypercube, crossed cube, Möbius cube, etc. are some examples of the n-dimensional BC graphs. In this paper, we propose a general method to study the edge-pancyclicity and path-embeddability of the BC graphs. First, we prove that a path of length l with dist(Xnxy) + 2 ? l ? 2n − 1 can be embedded between x and y with dilation 1 in Xn for xy ∈ V(Xn) with x ≠ y in Xn, where Xn (n ? 4) is a n-dimensional BC graph satisfying the three specific conditions and V(Xn) is the node set of Xn. Furthermore, by this result, we can claim that Xn is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Möbius cubes, but also other BC graphs except crossed cubes and Möbius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Möbius cubes.  相似文献   

12.
The n-dimensional locally twisted cube LTQn is a new variant of the hypercube, which possesses some properties superior to the hypercube. This paper investigates the fault-tolerant edge-pancyclicity of LTQn, and shows that if LTQn (n ? 3) contains at most n − 3 faulty vertices and/or edges then, for any fault-free edge e and any integer ? with 6 ? ? ? 2n − fv, there is a fault-free cycle of length ? containing the edge e, where fv is the number of faulty vertices. The result is optimal in some senses. The proof is based on the recursive structure of LTQn.  相似文献   

13.
The process of identifying faulty processors is called the diagnosis of the system. Several diagnostic models have been proposed, the most popular is the PMC (Preparata, Metze and Chen) diagnostic model. The pessimistic diagnosis strategy is a classic strategy based on the PMC model in which isolates all faulty nodes within a set containing at most one fault-free node. A system is t/tt/t-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistaken as a faulty one. The pessimistic diagnosability of a system G  , denoted by tp(G)tp(G), is the maximal number of faulty processors so that the system G   is t/tt/t-diagnosable. Jwo et al. [11] introduced the alternating group graph as an interconnection network topology for computing systems. The proposed graph has many advantages over hypercubes and star graphs. For example, for all alternating group graphs, every pair of vertices in the graph are connected by a Hamiltonian path and the graph can embed cycles with arbitrary length with dilation 1. In this article, we completely determine the pessimistic diagnosability of an n  -dimensional alternating group graph, denoted by AGnAGn. Furthermore, tp(AGn)=4n−11tp(AGn)=4n11 for n≥4n4.  相似文献   

14.
The connectivity is an important criteria to measure the fault-tolerant performance of a graph. However, the connectivity based on the condition of the set of arbitrary faulty nodes is generally lower. In this paper, in order to heighten this measure, we introduce the restricted connectivity into bijective connection networks. First, we prove that the probability that all the neighbors of an arbitrary node becomes faulty in any n-dimensional bijective connection network Xn is very low when n becomes sufficient large. Then, we give a constructive proof that under the condition that each node of an n-dimensional bijective connection network Xn has at least one fault-free neighbor, its restricted connectivity is 2n − 2, about half of the connectivity of Xn. Finally, by our constructive proof, we give an O(n) algorithm to get a reliable path of length at most n + 3⌈log2F∣⌉ + 1 between any two fault-free nodes in an n-dimensional bijective connection network. In particular, since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., our algorithm is appropriate for these cubes.  相似文献   

15.
The crossed cube, which is a variation of the hypercube, possesses some properties that are superior to those of the hypercube. In this paper, we show that with the assumption of each node incident with at least two fault-free links, an n-dimensional crossed cube with up to 2n−5 link faults can embed, with dilation one, fault-free cycles of lengths ranging from 4 to 2 n . The assumption is meaningful, for its occurrence probability is very close to 1, and the result is optimal with respect to the number of link faults tolerated. Consequently, it is very probable that algorithms executable on rings of lengths ranging from 4 to 2 n can be applied to an n-dimensional crossed cube with up to 2n−5 link faults.
Gen-Huey ChenEmail:
  相似文献   

16.
This work describes a novel routing algorithm for constructing a container of width n − 1 between a pair of vertices in an (n, k)-star graph with connectivity n − 1. Since Lin et al. [T.C. Lin, D.R. Duh, H.C. Cheng, Wide diameter of (n, k)-star networks, in: Proceedings of the International Conference on Computing, Communications and Control Technologies, vol. 5, 2004, pp. 160-165] already calculated the wide diameters in (n, n − 1)-star and (n, 1)-star graphs, this study only considers an (n, k)-star with 2 ? k ? n − 2. The length of the longest container among all constructed containers serves as the upper bound of the wide diameter of an (n, k)-star graph. The lower bound of the wide diameter of an (n, k)-star graph with 2 ? k ? ⌊n/2⌋ and the lower bound of the wide diameter of a regular graph with a connectivity of 2 or above are also computed. Measurement results indicate that the wide diameter of an (n, k)-star graph is its diameter plus 2 for 2 ? k ? ⌊n/2⌋, or its diameter plus a value between 1 and 2 for ⌊n/2⌋ + 1 ? k ? n − 2.  相似文献   

17.
Let G(VE) be a connected undirected graph with n vertices and m edges, where each vertex v is associated with a cost C(v) and each edge e = (uv) is associated with two weights, W(u → v) and W(v → u). The issue of assigning an orientation to each edge so that G becomes a directed graph is resolved in this paper. Determining a scheme to assign orientations of all edges such that maxxV{C(x)+∑xzW(xz)} is minimized is the objective. This issue is called the edge-orientation problem (the EOP). Two variants of the EOP, the Out-Degree-EOP and the Vertex-Weighted EOP, are first proposed and then efficient algorithms for solving them on general graphs are designed. Ascertaining that the EOP is NP-hard on bipartite graphs and chordal graphs is the second result. Finally, an O(n log n)-time algorithm for the EOP on trees is designed. In general, the algorithmic results in this paper facilitate the implementation of the weighted fair queuing (WFQ) on real networks. The objective of the WFQ is to assign an effective weight for each flow to enhance link utilization. Our findings consequently can be easily extended to other classes of graphs, such as cactus graphs, block graphs, and interval graphs.  相似文献   

18.
《Parallel Computing》2007,33(7-8):488-496
The star graph possesses many nice topological properties. In this study, we show that for any n-dimensional star graph (n  4) with ⩽2n  7 edge faults in which each node is incident to at least two non-faulty edges, there exists a fault-free Hamiltonian cycle. Compared with the corresponding study in hypercube, our method is rather succinct. Additionally, we also show the probability that an n dimensional star graph with arbitrary 2n  7 faulty edges at most is Hamiltonian is very close to one.  相似文献   

19.
The hypercube has been widely used as the interconnection network in parallel computers. The n-dimensional hypercube Qn is a graph having n2 vertices each labeled with a distinct n-bit binary strings. Two vertices are linked by an edge if and only if their addresses differ exactly in the one bit position. Let fv denote the number of faulty vertices in Qn. For n?3, in this paper, we prove that every fault-free edge and fault-free vertex of Qn lies on a fault-free cycle of every even length from 4 to n2−2fv inclusive even if fv?n−2. Our results are optimal.  相似文献   

20.
Navid Imani 《Information Sciences》2010,180(14):2802-2813
This paper introduces a new class of interconnection networks named star-pyramid. An n-level star-pyramid is formed by piling up star graphs of dimensions 1 to n in a hierarchy, connecting any node in each i-dimensional star, 1 < i ? n, to a node in the (i − 1)-dimensional star whose index is reached by removing the i symbol from the index of the former node in the i-dimensional star graph. Having extracted the properties of the new topology, featuring topological properties, a minimal routing algorithm, a simple but efficient broadcast algorithm, Hamiltonicity and pancyclicity, we then compare the network properties of the proposed topology and the well-known pyramid topology. We show that the star-pyramid has some more attractive properties than its equivalent pyramid. Finally, we propose two variants of star-pyramid, namely the generic star-pyramid and wrapped star-pyramid, as topologies with improved scalability, fault-tolerance, and diameter.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号