Browsing by Author "Shih, Lun-Min"

Now showing 1 - 6 of 6

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.
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.
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.
Fault-tolerant Maximal Local-Connectivity on the Bubble-sort Graphs
(2009)
Shih, Lun-Min
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processor and communication links, respectively. The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices to be maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we introduce the one-to-many version of connectivity. We show that an n-dimensional Bubble-sort Graph is maximally local-connected, even if there are at most n-3 faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.
Single-hidden-layer feed-forward quantum neural network based on Grover learning
(2013-09-01)
Liu, Cheng-Yi
;
Chen, Chein
;
Chang, Ching-Ter
;
Shih, Lun-Min
;
資訊工程學系
In this paper, a novel single-hidden-layer feed-forward quantum neural network model is proposed based on some concepts and principles in the quantum theory. By combining the quantum mechanism with the feed-forward neural network, we defined quantum hidden neurons and connected quantum weights, and used them as the fundamental information processing unit in a single-hidden-layer feed-forward neural network. The quantum neurons make a wide range of nonlinear functions serve as the activation functions in the hidden layer of the network, and the Grover searching algorithm outstands the optimal parameter setting iteratively and thus makes very efficient neural network learning possible. The quantum neuron and weights, along with a Grover searching algorithm based learning, result in a novel and efficient neural network characteristic of reduced network, high efficient training and prospect application in future. Some simulations are taken to investigate the performance of the proposed quantum network and the result show that it can achieve accurate learning. (C) 2013 Elsevier Ltd. All rights reserved.
Strong Menger connectivity with conditional faults on the class of hypercube-like networks
(2008-04-15)
Shih, Lun-Min
;
Chiang, Chieh-Feng
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
資訊工程學系
In this paper, we study the Menger property on a class of hypercube-like networks. We show that in all n-dimensional hypercubelike networks with n - 2 vertices removed, every pair of unremoved vertices u and v are connected by min{deg(u), deg(v)} vertex-disjoint paths, where deg(u) and deg(v) are the remaining degree of vertices u and v, respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to 2n - 5 vertex faults. (C) 2007 Elsevier B.V. All rights reserved.