Browsing by Author "Tan, JJM"

Now showing 1 - 20 of 21

Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes
(2003-07-31)
Li, TK
;
Tsai, CH
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to I V(G) I inclusive. It has been shown that Q(n) is bipancyclic if and only if n greater than or equal to 2. In this paper, we improve this result by showing that every edge of Q(n) - E' lies on a cycle of every even length from 4 to V(G) inclusive where E' is a subset of E(Q(n)) with E' less than or equal to n - 2. The result is proved to be optimal. To get this result, we also prove that there exists a path of length I joining any two different vertices x and y of Qn when h (x, y) less than or equal to l less than or equal to V(G) - 1 and l - h (x, y) is even where It (x, y) is the Hamming distance between x and y. (C) 2003 Elsevier Science B.V. All rights reserved.
Conditional diagnosability measures for large multiprocessor systems
(2005-02-01)
Lai, PL
;
Tan, JJM
;
Chang, CP
;
Hsu, LH
;
資訊工程學系
Diagnosability has played an important role in the reliability of an interconnection network. The classical problem of fault diagnosis is discussed widely and the diagnosability of many well-known networks have been explored. In this paper, we introduce a new measure of diagnosability, called conditional diagnosability, by restricting that any faulty set cannot contain all the neighbors of any vertex in the graph. Based on this requirement, the conditional diagnosability of the n-dimensional hypercube is shown to be 4(n - 2) + 1, which is about four times as large as the classical diagnosability. Besides, we propose some useful conditions for verifying if a system is t-diagnosable and introduce a new concept, called a strongly t-diagnosable system, under the PMC model. Applying these concepts and conditions, we investigate some t-diagnosable networks which are also strongly t-diagnosable.
Construction schemes for fault-tolerant Hamiltonian graphs
(2000-05-01)
Wang, JJ
;
Hung, CN
;
Tan, JJM
;
Hsu, LH
;
Sung, TY
In this paper, we present three construction schemes for fault-tolerant Hamiltonian graphs. We show that applying these construction schemes on fault-tolerant Hamiltonian graphs generates graphs preserving the original Hamiltonicity property. We apply these construction schemes to generate some known families of optimal 1-Hamiltonian graphs in the literature and the Hamiltonicity properties of these graphs are the direct consequence of the construction schemes. In addition, we can use these construction schemes to propose new family of optimal 1-Hamiltonian graphs. (C) 2000 John Wiley & Sons, Inc.
Cycles in highly faulty hypercubes
(2005)
Yang, MC
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
The hypercube Q(n) is one of the most popular networks. In, this paper, we first prove that the n-dimensional hypercube is 2n - 5 conditional fault- bipancyclic. That is, an injured hypercube with up to 2n - 5 faulty links has a cycle of length I for every even 4 <= l <= 2(n) when each node of the hypercube is incident with at least two healthy links. In addition, if a certain node is incident with less than two healthy links, we show that an injured hypercube contains cycles of all even lengths except hamiltonian cycles with up to 2n - 3 faulty links. Furthermore, the above two results are optimal. In conclusion, we find cycles of all possible lengths in injured hypercubes with up to 2n - 5 faulty links under all possible fault distributions.
Diagnosability of t-connected networks and product networks under the comparison diagnosis model
(2004-12-01)
Chang, CP
;
Lai, PL
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
Diagnosability is an important factor in measuring the reliability of an interconnection network, while the (node) connectivity is used to measure the fault tolerance of an interconnection network. We observe that there is a close relationship between the connectivity and the diagnosability. According to our results, a t-regular and t-connected network with at least 2t + 3 nodes is t-diagnosable. Furthermore, the diagnosability of the product networks is also investigated in this work. The product networks, including hypercube, mesh, and tori, comprise very important classes of interconnection networks. Herein, different combinations of t-diagnosable and t-connected are employed to study the diagnosability of the product networks.
Diagnosability of t-connected networks and product networks under the comparison diagnosis model
(2004-12-01)
Chang, CP
;
Lai, PL
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
Diagnosability is an important factor in measuring the reliability of an interconnection network, while the (node) connectivity is used to measure the fault tolerance of an interconnection network. We observe that there is a close relationship between the connectivity and the diagnosability. According to our results, a t-regular and t-connected network with at least 2t + 3 nodes is t-diagnosable. Furthermore, the diagnosability of the product networks is also investigated in this work. The product networks, including hypercube, mesh, and tori, comprise very important classes of interconnection networks. Herein, different combinations of t-diagnosable and t-connected are employed to study the diagnosability of the product networks.
Fault Hamiltonicity and fault Hamiltonian connectivity of the (n, k)-star graphs
(2003-12-01)
Hsu, HC
;
Hsieh, YL
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
In this paper, we consider the fault Hamiltonicity, and the fault Hamiltonian connectivity of the (n, k)-star graph S-n,S-k. Assume that F subset of V(S-n,S-k) boolean OR E(S-n,S-k). For n - k greater than or equal to 2, we prove that S-n,S-k - F is Hamiltonian if F less than or equal to n - 3 and S-n,S-k - F is Hamiltonian connected if F less than or equal to n - 4. For n - k = 1, S-n,S-n-1 is isomorphic to the n-star graph S-n which is known to be Hamiltonian if and only if n > 2 and Hamiltonian connected if and only if n = 2. Moreover, all the bounds are tight. (C) 2003 Wiley Periodicals, Inc.
Fault hamiltonicity and fault hamiltonian connectivity of the arrangement graphs
(2004-01-01)
Hsu, HC
;
Li, TK
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
The arrangement graph A(n,k) is a generalization of the star graph. There are some results concerning fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graph. However, these results are restricted in some particular cases and, thus, are less completed. In this paper, we improve these results and obtain a stronger and simpler statement. Let n - k greater than or equal to 2 and F subset of or equal to V(A(n,k)) boolean OR E(A(n,k)). We prove that A(n,k) - F is Hamiltonian if F less than or equal to k(n - k) - 2 and A(n,k) - F is Hamiltonian connected if F less than or equal to k(n - k) - 3. These results are optimal.
Fault-tolerant cycle-embedding of crossed cubes
(2003-11-30)
Yang, MC
;
Li, TK
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
The crossed cube CQ(n) introduced by Efe has many properties similar to those of the popular hypercube. However, the diameter of CQ(n) is about one half of that of the hypercube. Failures of links and nodes in an interconnection network are inevitable. Hence, in this paper, we consider the hybrid fault-tolerant capability of the crossed cube. Letting f(e) and f(v) be the numbers of faulty edges and vertices in CQ(n), we show that a cycle of length 1, for any 4 less than or equal to l less than or equal to V(CQ(n)) - f(v) can be embedded into a wounded crossed cube as long as the total number of faults (f(v) +f(e)) is no more than n - 2, and we say that CQ(n) is (n - 2)-fault-tolerant pancyclic. This result is optimal in the sense that if there are n - 1 faults, there is no guarantee of having a cycle of a certain length in it. (C) 2003 Published by Elsevier B.V.
Fault-tolerant hamiltonian laceability of hypercubes
(2002-09-30)
Tsai, CH
;
Tan, JJM
;
Liang, TN
;
Hsu, LH
;
資訊工程學系
It is known that every hypercube Q(n) is a bipartite graph. Assume that n greater than or equal to 2 and F is a subset of edges with F less than or equal to n - 2. We prove that there exists a hamiltonian path in Q(n) - F between any two vertices of different partite sets. Moreover, there exists a path of length 2(n) - 2 between any two vertices of the same partite set. Assume that n greater than or equal to 3 and F is a subset of edges with F less than or equal to n - 3. We prove that there exists a hamiltonian path in Q(n) - {v} - F between any two vertices in the partite set without v. Furthermore, all bounds are tight. (C) 2002 Elsevier Science B.V. All rights reserved.
Fault-tolerant hamiltonicity of twisted cubes
(2002-04-01)
Huang, WT
;
Tan, JJM
;
Hung, CN
;
Hsu, LH
;
資訊工程學系
The twisted cube TQ(n), is derived by changing some connection of hypercube Q(n) according to specific rules. Recently, many topological properties of this variation cube are studied. In this paper, we consider a faulty twisted n-cube with both edge and/or node faults. Let F be a subset of V(TQ(n)) boolean AND E(TQ(n)), we prove that TQ(n) - F remains hamiltonian if F less than or equal to n - 2. Moreover, we prove that there exists a hamiltonian path in TQ, - F joining any two vertices u, v in V(TQ(n)) - F if F less than or equal to n-3. The result is optimum in the sense that the fault-tolerant hamiltonicity (fault-tolerant hamiltonian connectivity respectively) of TQn is at most n-2 (n-3 respectively). (C) 2002 Elsevier Science (USA).
Fault-tolerant pancyclicity of the Mobius cubes
(2005-01-01)
Yang, MC
;
Li, TK
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
The Mobius cube MQ(n) proposed by Cull et al. is an alternative to the popular hypercube network. Recently, MQ(n) was shown to be pancyclic, i.e., cycles of any,lengths at least four can be embedded into it. Due to the importance of the fault tolerance in the parallel processing area, in this paper, we study an injured MQ(n) with mixed node and link faults. We show that it is (n - 2)-fault-tolerant pancyclic for n greater than or equal to 3, that is, an injured n-dimensional MQ(n) is still pancyclic with up to (n - 2) faults. Furthermore, our result is optimal.
Honeycomb rectangular disks
(2005-03-01)
Teng, YH
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a variation of honeycomb meshes. A honeycomb rectangular disk HReD(m,n) is obtained from the honeycomb rectangular mesh HReM(m,n) by adding a boundary cycle. A honeycomb rectangular disk HReD(m,n) is a 3-regular planar graph. It is obvious that the honeycomb rectangular mesh HReM(m,n) is a subgraph of HReD(m,n). We also prove that HReD(m,n) is hamiltonian. Moreover, HReD(m,n) -f remains hamiltonian for any f is an element of V(HReD(m, n)) boolean OR E(HReD(m, n)) if n >= 6. (c) 2005 Elsevier B.V. All rights reserved.
On embed-ding cycles into faulty twisted cubes
(2006-03-22)
Yang, MC
;
Li, TK
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
The twisted cube TQ(n) is an alternative to the popular hypercube network. Recently, some interesting properties of TQ(n) were investigated. In this paper, we study the pancycle problem on faulty twisted cubes. Let f(e) and f(v) be the numbers of faulty edges and faulty vertices in TQ(n), respectively. We show that, with f(e) + f(v) <= n - 2, a faulty TQ(n) still contains a cycle of length l for every 4 <= l < V(TQ(n)) - f(v) and odd integer n >= 3. (C) 2005 Elsevier Inc. All rights reserved.
On mutually independent hamiltonian paths
(2006-04-01)
Teng, YH
;
Tan, JJM
;
Ho, TY
;
Hsu, LH
;
資訊工程學系
Let P-1=< v(1), v(2), v(3),...,v(n)> and P-2=< u(1), u(2), u(3),...,u(n)> be two hamiltonian paths of G. We say that P-1 and P-2 are independent if u(1)=v(1), u(n)=v(n), and u(i)not equal v(i) for 1= 4. We prove that there are at least n-2-(e) over bar mutually independent hamiltonian paths between any pair of distinct vertices of G except n=5 and (e) over bar =1. Assume that G is a graph with the degree sum of any two non-adjacent vertices being at least n+2. Let u and v be any two distinct vertices of G. We prove that there are deg(G)(u)+deg(G)(v)-n mutually independent hamiltonian paths between u and v if (u, v) is an element of E (G) and there are deg(G)(u)+deg(G)(v)-n+2 mutually independent hamiltonian paths between u and v if otherwise. (C) 2005 Elsevier Ltd. All rights reserved.
On some super fault-tolerant Hamiltonian graphs
(2004-01-30)
Chen, YC
;
Tsai, CH
;
Hsu, LH
;
Tan, JJM
;
資訊工程學系
A k-regular Hamiltonian and Hamiltonian connected graph G is super fault-tolerant Hamiltonian if G remains Hamiltonian after removing at most k - 2 nodes and/or edges and remains Hamiltonian connected after removing at most k - 3 nodes and/or edges. A super fault-tolerant Hamiltonian graph has a certain optimal flavor with respect to the fault-tolerant Hamiltonicity and Hamiltonian connectivity. In this paper, we investigate a construction scheme to construct super fault-tolerant Hamiltonian graphs. In particularly, twisted-cubes, crossed-cubes, and Mobius cubes are all special cases of this construction scheme. Therefore, they are all super fault-tolerant Hamiltonian graphs. (C) 2003 Elsevier Inc. All rights reserved.
On the fault-tolerant Hamiltonicity of faulty crossed cubes
(2002-06-01)
Huang, WT
;
Chuang, YC
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
An n-dimensional crossed cube, CQ(n), is a variation of the hypercube. In this paper, we prove that CQ(n) is (n-2)-Hamiltonian and (n-3)-Hamiltonian connected. That is, a ring of length 2(n)-f(v) can be embedded in a faulty CQ(n) with f(v) faulty nodes and f(e) faulty edges, where f(v)+f(e) less than or equal to n-2 and n greater than or equal to 3. In other words, we show that the faulty CQ(n) is still Hamiltonian with n-2 faults. In addition, we also prove that there exists a Hamiltonian path between any pair of vertices in a faulty CQ(n) with n-3 faults. The above results are optimum in the sense that the fault-tolerant Hamiltonicity (fault-tolerant Hamiltonian connectivity respectively) Of CQ(n) is at most n-2 (n-3 respectively). A recent result has shown that a ring of length 2(n)-2f(v) can be embedded in a faulty hypercube, if f(v)+f(e) less than or equal to n-1 and n greater than or equal to 4, with a few additional constraints [17]. Our results, in comparison to the hypercube, show that longer rings can be embedded in CQ(n) without additional constraints.
Super-connectivity and super-edge-connectivity for some interconnection networks
(2003-08-10)
Chen, YC
;
Tan, JJM
;
Hsu, LH
;
Kao, SS
;
資訊工程學系
Let G = (V, E) be a k-regular graph with connectivity K and edge connectivity. G is maximum connected if kappa = k, and G is maximum edge connected if lambda = k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x(v,x) is an element of E} for some vertex v is an element of V; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)(v,x) is an element of E} for some vertex v is an element of V. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, mobius cubes, split-stars, and recursive circulant graphs. (C) 2002 Elsevier Science Inc. All rights reserved.
The diagnosability of the matching composition network under the comparison diagnosis model
(2004-08-01)
Lai, PL
;
Tan, JJM
;
Tsai, CH
;
Hsu, LH
;
資訊工程學系
The classical problem of diagnosability is discussed widely and the diagnosability of many well-known networks have been explored. In this paper, we consider the diagnosability of a family of networks, called the Matching Composition Network (MCN); two components are connected by a perfect matching. The diagnosability of MCN under the comparison model is shown to be one larger than that of the component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the Hypercube Q(n), the Crossed cube CQ(n), the Twisted cube TQ(n), and the Mobius cube MQ(n) can all be proven to be n, for n greater than or equal to 4. In particular, we show that the diagnosability of the four-dimensional Hypercube Q(4) is 4, which is not previously known.
The shuffle-cubes and their generalization
(2001-01-31)
Li, TK
;
Tan, JJM
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
In this paper, we first present a new variation of hypercubes, denoted by SQ(n) .SQ(n) is obtained from Q(n) by changing some links. Sa, is also an n-regular n-connected graph but of diameter about n/4. Then, we present a generalization of Se,. For any positive integer g, we can construct an n-dimensional generalized shuffle-cube with 2(n) vertices which is n-regular and n-connected. However its diameter can be about n/g if we consider g as a constant. (C) 2001 Elsevier Science B.V. All rights reserved.