Browsing by Author "Tan, Jimmy J. M."

Now showing 1 - 20 of 67

4-ordered-Hamiltonian problems of the generalized Petersen graph GP(n, 4)
(2013-02-01)
Hung, Chun-Nan
;
Lu, David
;
Jia, Randy
;
Lin, Cheng-Kuan
;
Liptak, Laszlo
A graph G is k-ordered if for every sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered-Hamiltonian if, in addition, the required cycle is a Hamiltonian cycle in G. The question of the existence of an infinite class of 3-regular 4-ordered-Hamiltonian graphs was posed in Ng and Schultz in 1997 [2]. At the time, the only known examples of such graphs were K-4 and K-3,K-3. Some progress was made by Meszaros in 2008 [21] when the Petersen graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered-Hamiltonian; moreover, an infinite class of 3-regular 4-ordered graphs was found. In 2010, a subclass of the generalized Petersen graphs was shown to be 4-ordered in Hsu et al. [9], with an infinite subset of this subclass being 4-ordered-Hamiltonian, thus answering the open question. However, these graphs are bipartite. In this paper we extend the result to another subclass of the generalized Petersen graphs. In particular, we find the first class of infinite non-bipartite graphs that are both 4-ordered-Hamiltonian and 4-ordered-Hamiltonian-connected, which can be seen as a solution to an extension of the question posted in Ng and Schultz in 1997 [2]. (A graph G is k-ordered-Hamiltonian-connected if for every sequence of k distinct vertices a(1), a(2),..., a(k) of G, there exists a Hamiltonian path in G from a(1) to a(k) where these k vertices appear in the specified order.) (C) 2012 Elsevier Ltd. All rights reserved.
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 local diagnosability measure for multiprocessor systems
(2007-05-01)
Hsu, Guo-Huang
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
The problem of fault diagnosis has been discussed widely and the diagnosability of many well-known networks has been explored. Under the PMC model, we introduce a new measure of diagnosability, called local diagnosability, and derive some structures for determining whether a vertex of a system is locally t-diagnosable. For a hypercube, we prove that the local diagnosability of each vertex is equal to its degree under the PMC model. Then, we propose a concept for system diagnosis, called the strong local diagnosability property. A system G(V; E) is said to have a strong local diagnosability property if the local diagnosability of each vertex is equal to its degree. We show that an n-dimensional hypercube Q(n) has this strong property, n >= 3. Next, we study the local diagnosability of a faulty hypercube. We prove that Q(n) keeps this strong property even if it has up to n - 2 faulty edges. Assuming that each vertex of a faulty hypercube Q(n) is incident with at least two fault-free edges, we prove Q(n) keeps this strong property even if it has up to 3(n - 2) - 1 faulty edges. Furthermore, we prove that Q(n) keeps this strong property no matter how many edges are faulty, provided that each vertex of a faulty hypercube Q(n) is incident with at least three fault-free edges. Our bounds on the number of faulty edges are all tight.
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.
A novel approach to comparison-based diagnosis for hypercube-like systems
(2008-01-01)
Chiang, Chieh-Feng
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
Interconnection network has been an active research area for parallel and distributed computer systems. The diagnosability is one of the important issues in the reliability of interconnection networks. In this paper, a novel idea on system diagnosis called local diagnosability is presented. The concept of local diagnosability is strongly related to the traditional global one. For this local sense, the status of every particular processor can be correctly identified. A sufficient condition is also proposed to determine the local diagnosability of a given processor. Following this local sense, we prove that the diagnosability of an n-dimensional hypercube-like network HLn is n for n >= 5, and show that in HLn with up to n - 2 faulty links, the local diagnosability of each processor equals to the connection links incident with it.
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.
An Algorithmic Approach to Conditional-Fault Local Diagnosis of Regular Multiprocessor Interconnected Systems under the PMC Model
(2013-03-01)
Lin, Cheng-Kuan
;
Kung, Tzu-Liang
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
System-level diagnosis is a crucial subject for maintaining the reliability of multiprocessor interconnected systems. Consider a system composed of N independent processors, each of which tests a subset of the others. Under the PMC diagnosis model, Dahbura and Masson [10] proposed an O(N-2,N-5) algorithm to identify the set of faulty processors in a t-diagnosable system, in which at most t processors are permanently faulty. In this paper, we establish some sufficient conditions so that a t-regular system can be conditionally (2t - 1)-diagnosable, provided every fault-free processor has at least one fault-free neighbor. Because any t-regular system is no more than t-diagnosable, the approached diagnostic capability is nearly double the classical one-step diagnosability. Furthermore, a correct and complete method is given which exploits these conditions and the presented branch-of-tree architecture to determine the fault status of any single processor. The proposed method has time complexity O(t(2)), and thus can diagnose the whole system in time O(t(2)N). In short, not only could the diagnostic capability be proved theoretically, but also it is feasible from an algorithmic perspective.
Component connectivity of the hypercubes
(2012)
Hsu, Lih-Hsing
;
Cheng, Eddie
;
Liptak, Laszlo
;
Tan, Jimmy J. M.
;
Lin, Cheng-Kuan
The r-component connectivity kappa(r)(G) of the non- complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. So, kappa(2) is the usual connectivity. In this paper, we determine the r-component connectivity of the hypercube Q(n) for r = 2, 3, ..., n + 1, and we classify all the corresponding optimal solutions.
Conditional diagnosability of hypercubes under the comparison diagnosis model
(2009-02-01)
Hsu, Guo-Huang
;
Chiang, Chieh-Feng
;
Shih, Lun-Min
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
Processor fault diagnosis plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. Lai et al. proposed a novel measure of diagnosability, called conditional diagnosability, by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. We make a contribution to the evaluation of diagnosability for hypercube networks under the comparison model and prove that the conditional diagnosability of n-dimensional Hypercube Q(n) is 3(n - 2) + 1 for n >= 5. The conditional diagnosability of Q. is about three times larger than the classical diagnosability of Q(n). (C) 2008 Elsevier B.V. All rights reserved.
Conditional fault hamiltonian connectivity of the complete graph
(2009-05-31)
Ho, Tung-Yang
;
Shih, Yuan-Kang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by B(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G - F is hamiltonian connected for every F C E(G) with |F| <= k and S(G - F) >= 3. The conditional edge-fault tolerant hamiltonian connectivity HC(e)(3)(G) is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n >= 4. We use K(n) to denote the complete graph with n vertices. In this paper, we show that HC(e)(3)(K(n)) = 2n - 10 for n is not an element of {4, 5, 8, 10}, HC(e)(3) (K(4)) = 0, HC(e)(3) (K(5)) = 2, HC(e)(3)(K(8)) = 5, and HC(e)(3)(K(10)) = 9. (c) 2009 Elsevier B.V. All rights reserved.
Conditional Fault Hamiltonicity of the Star Graph
(2014-01-01)
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
Cheng, Eddie
;
Liptak, Laszlo
Fault tolerance is an important property on network performance. A graph G is k-edge-fault conditional hamiltonian if G - F is hamiltonian for every F subset of E(G) with vertical bar F vertical bar <= k and delta(G - F) >= 2. In this paper we show that for n >= 4 the n-dimensional star graph S-n is (3n - 10)-edge-fault conditional hamiltonian.
CONDITIONAL MATCHING PRECLUSION FOR THE STAR GRAPHS
(2015-04-01)
Cheng, Eddie
;
Liptak, Laszlo
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
Lin, Cheng-Kuan
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those incident to a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those incident to a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number and classify all optimal sets for the star graphs, one of the most popular interconnection networks.
Conditional-Fault Diagnosability of Multiprocessor Systems with an Efficient Local Diagnosis Algorithm under the PMC Model
(2011-10-01)
Lin, Cheng-Kuan
;
Kung, Tzu-Liang
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
Diagnosis is an essential subject for the reliability of multiprocessor systems. Under the PMC diagnosis model, Dahbura and Masson [12] proposed a polynomial-time algorithm with time complexity O(N(2.5)) to identify all the faulty processors in a system with N processors. In this paper, we present a novel method to diagnose a conditionally faulty system by applying the concept behind the local diagnosis, introduced by Somani and Agarwal [30], and formalized by Hsu and Tan [18]. The goal of local diagnosis is to identify the fault status of any single processor correctly. Under the PMC diagnosis model, we give a sufficient condition to estimate the local diagnosability of a given processor. Furthermore, we propose a helpful structure, called the augmenting star, to efficiently determine the fault status of each processor. For an N-processor system in which every processor has an O(log N) degree, the time complexity of our algorithm to diagnose any given processor is O((log N)(2)), provided that each processor can construct an augmenting star structure of full order in time O((log N)(2)) and the time for a processor to test another one is constant. Therefore, the time totals to O(N(log N)(2)) for diagnosing the whole system.
Diagnosability of star graphs with missing edges
(2012-04-01)
Chiang, Chieh-Feng
;
Hsu, Guo-Huang
;
Shih, Lun-Min
;
Tan, Jimmy J. M.
;
資訊工程學系
In this paper, we study the system diagnosis on an n-dimensional star under the comparison model. Following the concept of local diagnosability [3], the strong local diagnosability property [7] is discussed; this property describes the equivalence of the local diagnosability of a node and its degree. We prove that an n-dimensional star has this property, and it keeps this strong property even if there exist n - 3 missing edges in it. (C) 2011 Elsevier Inc. All rights reserved.
Disjoint cycles in hypercubes with prescribed vertices in each cycle
(2013-12-01)
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
Kung, Tzu-Liang
;
資訊工程學系
A graph G is spanning r-cyclable of order t if for any r nonempty mutually disjoint vertex subsets A(1), A(2) ,..., A(r) of G with vertical bar A(1) boolean OR A(2) boolean OR ... boolean OR A(r)vertical bar <= t, there exist r disjoint cycles C-1, C-2,...,Cr of G such that C-1 boolean OR C-2 boolean OR ... C-r spans G, and C-t contains A(i) for every i. In this paper, we prove that the n-dimensional hypercube Q(n) is spanning 2-cyclable of order n - 1 for n >= 3. Moreover, Q(n) is spanning k-cyclable of order k if k <= n - 1 for n >= 2. The spanning r-cyclability of a graph G is the maximum integer t such that G is spanning r-cyclable of order k for k = r, r + 1,..., t but is not spanning r-cyclable of order t + 1. We also show that the spanning 2-cyclability of Q(n) is n - for n >= 3. (C) 2013 Elsevier B.V. All rights reserved.
Edge-bipancyclicity of conditional faulty hypercubes
(2007-12-31)
Shih, Lun-Min
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
Xu et al. showed that for any set of faulty edges F of an n-dimensional hypercube Q(n) with vertical bar F vertical bar <= n - 1, each edge of Q(n) - F lies on a cycle of every even length from 6 to 2(n), n >= 4, provided not all edges in F are incident with the same vertex. In this paper, we find that under similar condition, the number of faulty edges can be much greater and the same result still holds. More precisely, we show that, for up to vertical bar F vertical bar = 2n - 5 faulty edges, each edge of the faulty hypercube Q(n) - F lies on a cycle of every even length from 6 to 2(n) with each vertex having at least two healthy edges adjacent to it, for n >= 3. Moreover, this result is optimal in the sense that there is a set F of 2n - 4 conditional faulty edges in Q(n) such that Q(n) - F contains no hamiltonian cycle. (c) 2007 Elsevier B.V. All rights reserved.
Embedding Hamiltonian paths in augmented cubes with a required vertex in a fixed position
(2009-11-01)
Lee, Chung-Meng
;
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
It is proved that there exists a path P(l)(x, y) of length l if d(AQn) (x, y) <= l <= 2(n) - 1 between any two distinct vertices x and y of AQ(n). Obviously, we expect that such a path P(l)(x, y) can be further extended by including the vertices not in P(l)(x, y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that there exists a hamiltonian path R(x, y, z;l) from x to z such that d(R(x,y,z;l)) (x, y) = l for any three distinct vertices x, y, and z of AQ(n) with n >= 2 and for any d(AQn) (x, y)<= l <= 2(n) - 1 - d(AQn) (y, z). Furthermore, there exists a hamiltonian cycle S(x, y; l) such that d(S(x,y;l)) (x, y) = l for any two distinct vertices x and y and for any d(AQn) (x, y) <= l <= 2(n-1). (C) 2009 Elsevier Ltd. All rights reserved.
Embedding hamiltonian paths in hypercubes with a required vertex in a fixed position
(2008-08-16)
Lee, Chung-Meng
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
Assume that n is a positive integer with n >= 2. It is proved that between any two different vertices x and y of Q(n) there exists a path PI(x, y) of length l for any l with h(x, y) <= l <= 2(n) - 1 and 2 vertical bar(l - h(x, y)). We expect such path P-l(x, y) can be further extended by including the vertices not in P-l(x, y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that for any two vertices x and z from different partite set of n-dimensional hypercube Q(n), for any vertex y is an element of V(Q(n)) - {x, z}, and for any integer I with h(x, y) <= l <= 2(n) - l - h(y, z) and 2 vertical bar(l - h(x, y)), there exists a hamiltonian path R(x, y, z; l) from x to z such that d(R(x,y,z,l))(x, y) = l. Moreover, for any two distinct vertices x and y of Q,, and for any integer I with h(x, y) <= l <= 2(n-1) and 2 vertical bar(l - h(x, y)), there exists a hamiltonian cycle S(x, y; l) such that d(S(X,y;l))(x, y) = l. (C) 2008 Elsevier B.V. All rights reserved.
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-free mutually independent Hamiltonian cycles of faulty star graphs
(2011)
Kung, Tzu-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG(n) denote an n-dimensional star network in which f <= n - 3 edges may fail accidentally. We show that there exist (n - 2 - f)-mutually independent Hamiltonian cycles rooted at any vertex in SGn if n epsilon {3, 4}, and there exist (n - 1 - f)-mutually independent Hamiltonian cycles rooted at any vertex in SG(n) if n >= 5.