Browsing by Author "Chen, Y-Chuang"

Now showing 1 - 10 of 10

A family of Hamiltonian and Hamiltonian connected graphs with fault tolerance
(2010-11-01)
Chen, Y-Chuang
;
Huang, Yong-Zen
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
資訊工程學系
Processor (vertex) faults and link (edge) faults may happen when a network is used, and it is meaningful to consider networks (graphs) with faulty processors and/or links. A k-regular Hamiltonian and Hamiltonian connected graph G is optimal fault-tolerant Hamiltonian and Hamiltonian connected if G remains Hamiltonian after removing at most k-2 vertices and/or edges and remains Hamiltonian connected after removing at most k-3 vertices and/or edges. In this paper, we investigate in constructing optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected graphs. Therefore, some of the generalized hypercubes, twisted-cubes, crossed-cubes, and Mobius cubes are optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected.
A recursively construction scheme for super fault-tolerant hamiltonian graphs
(2006-06-15)
Chen, Y-Chuang
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
For the interconnection network topology, it is usually represented by a graph. When a network is used. processors and/or links faults may happen. Thus, it is meaningful to consider faulty networks, We consider k-regular graphs in this paper. We define a k-regular hamiltonian and hamiltonian connected graph G is super fault-tolerant hamiltonian if G remains hamiltonian after removing at most k - 2 vertices and/or edges and remains hamiltonian connected after removing at most k - 3 vertices and/or edges. A Super fault-tolerant hamiltonian graph has a certain optimal flavor with respect to the fault tolerant hamiltonicity and fault-tolerant hamiltonian connectivity. The aim of this paper is to investigate a construction scheme to construct various super fault-tolerant hamiltonian graphs. Along the way. the recursire circulant graph is a special case of our construction scheme. and the super fault-tolerant hamiltonian property of recursive circulant graph is obtained. (c) 2005 Elsevier Inc. All rights reserved.
Hamiltonian decomposition of generalized recursive circulant graphs
(2016-09)
Chen, Y-Chuang
;
Tsai, Tsung-Han
;
資訊工程學系
;
Department of Computer Science
In 2012, Tang et al. [9] proposed a new class of graphs called generalized recursive circulant (GRC) graphs, which is an extension of recursive circulant graphs. GRC graphs have a more flexible structure than recursive circulant graphs, while retaining their attractive properties, such as degree, connectivity, diameter, and routing algorithm. In this paper, the Hamiltonian decomposition of some GRC graphs is discussed. (C) 2016 Elsevier B.V. All rights reserved.
Maximally local connectivity and connected components of augmented cubes
(2014-07-20)
Chen, Y-Chuang
;
Chen, Meng-Hung
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
The connectivity of a graph is an important issue in graph theory, and is also one of the most important factors in evaluating the reliability and fault tolerance of a network. It is known that the augmented cube AQ is maximally connected, i.e. (2n - 1)-connected, for n >= 4. By the classic Menger\'s Theorem, every pair of vertices in AQ is connected by 2n - 1 vertex-disjoint paths for n >= 4. A routing with parallel paths can speed up transfers of large amounts of data and increase fault tolerance. Motivated by research on networks with faults, we obtained the result that for any faulty vertex set F c V(AQ) and [F] < 2n - 7 for n >= 4, each pair of non-faulty vertices, denoted by u and v, in AQ F is connected by min{deg(f)(u), deg(f) (v)} vertex-disjoint fault-free paths, where degf(u) and degf(v) are the degree of u and v in AQ(n) - F, respectively. Moreover, we demonstrate that for any faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar < 4n - 9 for n 4, there exists a large connected component with at least 2(n) - vertical bar F vertical bar 1 vertices in AQ F, which improves on the results of Ma et al. (2008) who show this for n >= 6. (C) 2014 Elsevier Inc. All rights reserved.
Maximally Local Connectivity on Augmented Cubes
(2009)
Chen, Y-Chuang
;
Chen, Meng-Hung
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
Connectivity is all important measurement for the fault tolerance in interconnection networks. It is known that the augmented cube AQ(n) is maximally connected, i.e. (2n - 1)-connected, for n >= 4. By the classical Menger\'s Theorem, every pair of vertices in AQ(n) is connected by 2n - 1 vertex-disjoint paths for n >= 4. A routing with parallel paths can speed up transfers of large amounts of data and increase fault tolerance. Motivated by some research works on networks with faults, we have a further result that for any faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 2n - 7 for n >= 4, each pair of non-faulty vertices, denoted by u and v, in AQ(n) - F is connected by min{deg(f)(u), deg(f)(v)} vertex-disjoint fault-free paths, where deg(f)(u) and deg(f)(v) are the degree of u and v in AQ(n) - F, respectively. Moreover, we have another result that for ally faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 4n - 9 for n >= 4, there exists a large connected component with at least 2(n) - vertical bar F vertical bar - 1 vertices in AQ(n) - F. In general, a remaining large fault-free connected component also increases fault tolerance.
Optimal Edge Congestion of Exchanged Hypercubes
(2016-01-01)
Tsai, Tsung-Han
;
Chen, Y-Chuang
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
Topological properties have become a popular and important area of focus for studies that analyze interconnections between networks. The hypercube is one of the most widely discussed topological structures for interconnections between networks and is usually covered in introductions to the basic principles and methods for network design. The exchanged hypercube EH(s, t) is a new variant of the hypercube that has slightly more than half as many edges and retains several valuable and desirable properties of the hypercube. In this paper, we propose an approach for shortest path routing algorithms from the source vertex to the destination vertex in EH(s, t) with time complexity O(n), where n - s + t + 1 and 1 <= s <= t. We focus on edge congestion, which is an important indicator for cost analyses and performance measurements in interconnection networks. Based on our shortest path routing algorithm, we show that the edge congestion of EH(s, t) is 3.2(s+t+1) - 2(s+1) - 2(t+1). In addition, we prove that our shortest path routing algorithm is an optimal routing strategy with respect to the edge congestion of EH(s, t).
Optimal Edge Congestion of Exchanged Hypercubes
(2016-01)
Tsai, Tsung-Han
;
Chen, Y-Chuang
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
Topological properties have become a popular and important area of focus for studies that analyze interconnections between networks. The hypercube is one of the most widely discussed topological structures for interconnections between networks and is usually covered in introductions to the basic principles and methods for network design. The exchanged hypercube EH(s, t) is a new variant of the hypercube that has slightly more than half as many edges and retains several valuable and desirable properties of the hypercube. In this paper, we propose an approach for shortest path routing algorithms from the source vertex to the destination vertex in EH(s, t) with time complexity O(n), where n - s + t + 1 and 1 <= s <= t. We focus on edge congestion, which is an important indicator for cost analyses and performance measurements in interconnection networks. Based on our shortest path routing algorithm, we show that the edge congestion of EH(s, t) is 3.2(s+t+1) - 2(s+1) - 2(t+1). In addition, we prove that our shortest path routing algorithm is an optimal routing strategy with respect to the edge congestion of EH(s, t).
Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs
(2008)
Chen, Y-Chuang
;
Huang, Yong-Zen
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
資訊工程學系
A k-regular hamiltonian and hamiltonian connected graph G is optimal fault-tolerant hamiltonian and hamiltonian connected 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. In this paper, we investigate a construction scheme to construct optimal fault-tolerant hamiltonian and hamiltonian connected graphs. Hence, some of the generalized hypercubes, Twisted-cubes, Crossed-cubes, and Mobius cubes are optimal fault-tolerant hamiltonian and optimal fault-tolerant hamiltonian connected.
Restricted connectivity for three families of interconnection networks
(2007-05-15)
Chen, Y-Chuang
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
Vertex connectivity and edge connectivity are two important parameters in interconnection networks. Even though they reflect the fault tolerance correctly, they undervalue the resilience of large networks. By the concept of conditional connectivity and super-connectivity, the concept of restricted vertex connectivity and restricted edge connectivity of graphs was proposed by Esfahanian [A.H. Esfahanian, Generalized measures of fault tolerance with application to N-cube networks, IEEE Transactions on Computers 38 (1989) 1586-1591]. Such measures take the resilience of large networks into consideration. In this paper, we propose three families of interconnection networks and discuss their restricted vertex connectivity and restricted edge connectivity. In particular, the hypercubes, twisted-cubes, crossed-cubes, mobius cubes, star graphs, pancake graphs, recursive circulant graphs, and k-ary n-cubes are special cases of these families. (c) 2006 Elsevier Inc. All rights reserved.
Topological Properties on the Wide and Fault Diameters of Exchanged Hypercubes
(2014-12-01)
Tsai, Tsung-Han
;
Chen, Y-Chuang
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
The n-dimensional hypercube is one of the most popular topological structure for interconnection networks in parallel computing and communication systems. The exchanged hypercube EH(s, t), a variant of the hypercube, retains several valuable and desirable properties of the hypercube such as a small diameter, bipancyclicity, and super connectivity. In this paper, we construct s + 1 (or t + 1) internally vertex-disjoint paths between any two vertices for parallel routes in the exchanged hypercube EH(s,t) for 3 <= s <= t. We also show that both the (s + 1)-wide diameter and s-fault diameter of the exchanged hypercube EH(s,t) are s + t + 3 for 3 <= s <= t.