Browsing by Author "Teng, Yuan-Hsiang"

Now showing 1 - 8 of 8

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.
Local Diagnosis Algorithms for Multiprocessor Systems Under the Comparison Diagnosis Model
(2013-12-01)
Lin, Cheng-Kuan
;
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
An efficient diagnosis is very important for a multiprocessor system. The ability to identify all the faulty devices in a multiprocessor system is known as diagnosability. In the comparison model, the diagnosis is performed by sending two identical signals from a processor to a pair of distinct neighbors, and then comparing their responses. Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N-5) to diagnose a system with a total number N of processors under the comparison model. Recently, some concepts, such as the conditional diagnosability and the local diagnosability, are concerned with the measure which is able to better reflect fault patterns in real systems. In this paper, we propose a specific structure, the balanced wind-bell-tree, and give an algorithm to determine the fault status of each processor for conditional local diagnosis under the comparison model. According to our results, a specific t-connected network with the balanced wind-bell-tree structure is conditionally (2t - 1)*-diagnosable, and the time complexity to diagnose all the faulty processors is O(N(log N)(2)) with our algorithm, where N is the total number of the processors in the network.
Panpositionable hamiltonicity and panconnectivity of the arrangement graphs
(2008-04-15)
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
The arrangement graph A(n,k) is a generalization of the star graph. It is more flexible in its size than the star graph. There are some results concerning hamiltonicity and pancyclicity of the arrangement graphs. In this paper, we propose a new concept called panpositionable hamiltonicity. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and for any integer l satisfying d(x,y) <= l <= vertical bar v(G)vertical bar - d(x,y), there exists a hamiltonian cycle C of G such that the relative distance between x and y on C is l. A graph G is panconnected if there exists a path of length l joining any two different vertices x and y with d(x,y) <= l <= vertical bar v(G)vertical bar - 1. We show that An, k is panpositionable hamiltonian and panconnected if k >= 1 and n - k >= 2. (c) 2007 Elsevier Inc. All rights reserved.
Panpositionable hamiltonicity of the alternating group graphs
(2007-09-01)
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
The alternating group graph AG(n) is an interconnection network topology based on the Cayley graph of the alternating group. There are some interesting results concerning the hamiltonicity and the fault tolerant hamiltonicity of the alternating group graphs. In this article, we propose a new concept called panpositionable harniltonicity. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and for any integer I satisfying d(x, y) <= I <= vertical bar V(G)vertical bar - d(x, y), there exists a hamiltonian cycle C of G such that the relative distance between x, y on C is I. We show that AG(n) is panpositionable hamiltonian if n >= 3. (C) 2007 Wiley Periodicals, Inc.
The globally Bi-3*-connected property of the honeycomb rectangular torus
(2007-12-15)
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
The honeycomb rectangular torus is an attractive alternative to existing networks such as mesh-connected networks in parallel and distributed applications because of its low network cost and well-structured connectivity. Assume that m and n are positive even integers with n >= 4. It is known that every honeycomb rectangular torus HReT(m, n) is a 3-regular bipartite graph. We prove that in any HReT(m, n), there exist three internally-disjoint spanning paths joining x and y whenever x and y belong to different partite sets. Moreover, for any pair of vertices x and y in the same partite set, there exists a vertex z in the partite set not containing x and y, such that there exist three internally-disjoint spanning paths of G - {z} joining x and y. Furthermore, for any three vertices x, y, and z of the same partite set there exist three internally-disjoint spanning paths of G - {z} joining x and y if and only if n >= 6 or m = 2. (C) 2007 Elsevier Inc. All rights reserved.
The paths embedding of the arrangement graphs with prescribed vertices in given position
(2012-11-01)
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Tsay, Chey-Woei
;
Hsu, Lih-Hsing
;
資訊工程學系
Let n and k be positive integers with n-ka parts per thousand yen2. The arrangement graph A (n,k) is recognized as an attractive interconnection networks. Let x, y, and z be three different vertices of A (n,k) . Let l be any integer with . We shall prove the following existance properties of Hamiltonian path: (1) for n-ka parts per thousand yen3 or (n,k)=(3,1), 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; (2) for n-k=2 and na parts per thousand yen5, there exists a Hamiltonian path R(x,y,z;l) except for the case that x, y, and z are adjacent to each other.
The spanning laceability on the faulty bipartite hypercube-like networks
(2013-04-01)
Lin, Cheng-Kuan
;
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
Marusic, Dragan
A w-container C(u, v) of a graph G is a set of w-disjoint paths joining u to v. A w-container of G is a w*-container if it contains all the nodes of V (G). A bipartite graph G is w*-laceable if there exists a w*-container between any two nodes from different parts of G. Let n and k be any two positive integers with n >= 2 and k <= n. In this paper, we prove that n-dimensional bipartite hypercube-like graphs are f-edge fault k*-laceable for every f <= n - 2 and f + k <= n. (C) 2013 Elsevier Inc. All rights reserved.
Three Round Adaptive Diagnosis with a Tree-Based Structure
(2011-01-01)
Lin, Cheng-Kuan
;
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
The ability of identifying all the faulty devices in a multiprocessor system is known as diagnosability. The PMC model is the tested-based diagnosis with a processor performing the diagnosis by testing on the neighboring processors via the links between them. In this paper, we propose a tree-based structure for local diagnosis under PMC model. We design a three round adaptive local diagnosis algorithm in the tree-based structure.