Browsing by Author "Kueng, Tz-Liang"

Now showing 1 - 5 of 5

A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
(2009-04-01)
Kueng, Tz-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
In the paper "Fault-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges" (J. Comb. Optim. 13:153-162, 2007), the authors claimed that an n-dimensional hypercube can be embedded with (n-1-f)-mutually independent Hamiltonian cycles when fa parts per thousand currency signn-2 faulty edges may occur accidentally. However, there are two mistakes in their proof. In this paper, we give examples to explain why the proof is deficient. Then we present a correct proof.
Embedding paths of variable lengths into hypercubes with conditional link-faults
(2009-08-01)
Kueng, Tz-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q(n), in which every node is still incident to at least two fault-free links. Then we show that Q(n) - F has a path of any odd (resp. even) length in the range from the distance to 2(n) - 1 (resp. 2(n) - 2) between two arbitrary nodes even if vertical bar F vertical bar = 2n - 5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults. (C) 2009 Elsevier B.V. All rights reserved.
Fault-tolerant hamiltonian connectedness of cycle composition networks
(2008-02-15)
Kueng, Tz-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
It is important for a network to tolerate as many faults as possible. With the graph representation of an interconnection network, a k-regular hamiltonian and hamiltonian connected network is super fault-tolerant hamiltonian if it remains hamiltonian after removing up to k - 2 vertices and/or edges and remains hamiltonian connected after removing up to k - 3 vertices and/or edges. Super fault-tolerant hamiltonian networks have an optimal flavor with regard to the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity. For this reason, a cycle composition framework was proposed to construct a (k + 2)-regular super fault-tolerant hamiltonian network based on a collection of n k-regular super fault-tolerant hamiltonian networks containing the same number of vertices for it n >= 3 and k >= 5. This paper is aimed to emphasize that the cycle composition framework can be still applied even when k = 4. (c) 2007 Elsevier Inc. All rights reserved.
Long paths in hypercubes with conditional node-faults
(2009-02-15)
Kueng, Tz-Liang
;
Liang, Tyne
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
資訊工程學系
Let F be a set of f <= 2n - 5 faulty nodes in an n-cube Q(n) such that every node of Q(n) still has at least two fault-free neighbors. Then we show that Q(n) - F contains a path of length at least 2(n) - 2f - 1 (respectively, 2(n) - 2f - 2) between any two nodes of odd (respectively, even) distance. Since the n-cube is bipartite, the path of length 2(n) - 2f - 1 (or 2(n) - 2f - 2) turns out to be the longest if all faulty nodes belong to the same partite set. As a contribution, our study improves upon the previous result presented by [J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults, Information Sciences 176 (2006) 759-771] where only n - 2 faulty nodes are considered. (c) 2008 Elsevier Inc. All rights reserved.
Mutually independent hamiltonian cycles of binary wrapped butterfly graphs
(2008-12-01)
Kueng, Tz-Liang
;
Liang, Tyne
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
Effective utilization of communication resources is crucial for improving performance in multiprocessor/communication systems. In this paper, the mutually independent hamiltonicity is addressed for its effective utilization of resources on the binary wrapped butterfly graph. Let G be a graph with N vertices. A hamiltonian cycle C of G is represented by < u(1),u(2),...,u(N),u(1)> to emphasize the order of vertices on C. Two hamiltonian cycles of G, namely C(1) = < u(1),u(2),...,u(N),u(1)> and C(2) = < v(1),v(2),...,v(N),v(1)>, are said to be independent if u(1) = v(1) and u(i) not equal v(i) for all 2 <= i <= N. A collection of m hamiltonian cycles C(1),...,C(m), starting from the same vertex, are m-mutually independent if any two different hamiltonian cycles are independent. The mutually independent hamiltonicity of a graph G, denoted by IHC(G), is defined to be the maximum integer m such that, for each vertex u of G, there exists a set of m-mutually independent hamiltonian cycles starting from u. Let BF(n) denote the n-dimensional binary wrapped butterfly graph. Then we prove that IHC(BF(n)) = 4 for all n >= 3. (C) 2008 Elsevier Ltd. All rights reserved.