Browsing by Author "Hung, CN"

Now showing 1 - 9 of 9

1-fault tolerant design for token rings
(1998)
Wang, JJ
;
Hung, CN
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper, we present a family of 3-regular, planar, and hamiltonian graphs. Any graph in this family remains hamiltonian if any node or any edge is deleted. Moreover, the diameter of any graph in this family is O(root p) where p is the number of nodes.
A response to Volgenant's addendum on the most vital edges
(1996-05-01)
Hung, CN
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
;
Department of Computer Science
Christmas tree: A versatile 1-fault-tolerant design for token rings
(1999-10-29)
Hung, CN
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
;
Department of Computer Science
The token ring topology is required in token passing approach used in distributed operating systems. Fault tolerance is also required in the designs of distributed systems. Note that 1-fault-tolerant design for token rings is equivalent to design of 1-Hamiltonian graphs. This paper introduces a new family of graphs called Christmas tree, denoted by CT(s). The graph CT(s) is a 3-regular, planar, 1-Hamiltonian, and Hamiltonian-connected graph. The number of nodes in CT(s) is 3.2(s) - 2. Its diameter is 1 if s = 1, 3 if s = 2, and 2s if s greater than or equal to 3. (C) 1999 Elsevier Science B.V. All rights reserved.
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.
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).
On the isomorphism between cyclic-cubes and wrapped butterfly networks
(2000-08-01)
Hung, CN
;
Wang, JJ
;
Sung, TY
;
Hsu, LH
;
資訊工程學系
We show that the cyclic-cubes defined by Ada W.C. Fu and S.C. Chau [1] are isomorphic to k-ary wrapped butterfly networks.
Optimal 1-Hamiltonian graphs
(1998-02-13)
Wang, JJ
;
Hung, CN
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper, we present a family of 3-regular, planar, and hamiltonian graphs. Any graph in this family remains hamiltonian if any node or any edge is deleted. Moreover, the diameter of any graph in this family is O(root p) where p is the number of nodes. (C) 1998 Elsevier Science B.V.
Ring embedding in faulty pancake graphs
(2003-06-15)
Hung, CN
;
Hsu, HC
;
Liang, KY
;
Hsu, LH
;
資訊工程學系
In this paper, we consider the fault hamiltonicity and the fault hamiltonian connectivity of the pancake graph P-n. Assume that F subset of or equal to V(P-n) boolean OR E(P-n). For n greater than or equal to 4, we prove that P-n - F is hamiltonian if F less than or equal to (n - 3) and P-n - F is hamiltonian connected if F less than or equal to (n - 4). Moreover, all the bounds are optimal. (C) 2003 Elsevier Science B.V. All rights reserved.
The correct diameter of trivalent Cayley graphs
(1999-11-26)
Tsai, CH
;
Hung, CN
;
Hsu, LH
;
Chang, CH
;
資訊工程學系
Let n be a positive integer with n greater than or equal to 2. The trivalent Cayley interconnection network, denoted by TCIN(n), is proposed by Vadapalli and Srimani (1995). Later, Vadapalli and Srimani (1996) claimed that the diameter of TCIN(n) is 2n - 1. In this paper, we argue that the above claim is not correct. Instead, we show that the diameter of TCIN(n) is 2n - 1 only for n = 2 and 2n - 2 for all other cases. (C) 1999 Elsevier Science B.V. All rights reserved.