Browsing by Author "Lin, Cheng-Kuan"

Now showing 1 - 20 of 42

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 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.
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.
Automatic Parameter Selection for the ZigBee Distributed Address Assignment Mechanism
(2013-01-01)
Hu, Shu-Chiung
;
Lin, Cheng-Kuan
;
Tseng, Yu-Chee
;
資訊工程學系
;
Department of Computer Science
Addressing in wireless sensor networks is to assign each newly-joining device a unique address. However, to allot the naming space in a large-scale distributed wireless sensor network is not an easy task. ZigBee is a popular communication standard for wireless sensor networks. It suggests a distributed address assignment mechanism. A parent device can calculate network addresses for its child devices without communicating with other devices. However, the parameter configuration of this mechanism strictly restricts the number of children of a device and the depth of the network. ZigBee does not recommend suitable parameters. The improper parameter configuration usually makes many devices isolated from the network which become orphan devices. In this paper, we propose two automatic parameter selection schemes for ZigBee address assignment scheme by probing the network and then selecting parameters in advance to alleviate the orphan problem. They can automatically suggest proper parameters for different network topologies and thus help the original ZigBee address assignment mechanism to effectively reduce orphans.
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 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.
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.
Distributed Address Assignment with Address Borrowing for ZigBee Networks
(2014-01-01)
Hu, Shu-Chiung
;
Lin, Cheng-Kuan
;
Tseng, Yu-Chee
;
Chen, Wen-Tsuen
;
資訊工程學系
ZigBee is a popular communication standard for wireless sensor networks. It suggests a distributed address assignment mechanism (DAAM), which is easy to implement but may restrict the number of children of a router and the depth of the network. Since DAAM is too conservative, the utilization of the 16-bit address pool may become poor, causing the orphan problem. In this paper, we propose a distributed address assignment scheme by allowing a parent to borrow a subtree of address space from a neighbor to alleviate the orphan problem. When a new node tries to associate with a parent router which has no free address, this parent router will inquire its 2hop neighbors for lending a subtree of free address space. We also propose a light-weight routing to support one-to-one routing in this environment.
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.
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.
Fault-Tolerant Hamiltonian Connectivity and Fault-Tolerant Hamiltonicity of the Fully Connected Cubic Networks
(2009-11-01)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
資訊工程學系
;
Department of Computer Science
Many papers on the fully connected cubic networks have been published for the past several years due to its favorite properties. In this paper, we consider the fault-tolerant hamiltonian connectivity and fault-tolerant hamiltonicity of the fully connected cubic network. We use FCCN(n) to denote the fully connected cubic network of level n. Let G = (V, E) be a graph. The fault-tolerant hamiltonian connectivity H(f)(k) (G) is defined to be the maximum integer l such that G - F remains hamiltonian connected for every F subset of V(G) boolean OR E(G) with vertical bar F vertical bar <= l. The fault-tolerant hamiltonicitly H(f)(G) is defined to be the maximum integer l such that G - F remains hamiltonian for every F subset of V(G) boolean OR E(G) with vertical bar F vertical bar <= l. We prove that H(f)(k) (FCCN(n)) = 0 and H(f)(FCCN(n)) = 1 if n >= 2.
Fault-tolerant hamiltonian connectivity of the WK-recursive networks
(2014-07-01)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
Many research on the WK-recursive network has been published during the past several years due to its favorite properties. In this paper, we consider the fault-tolerant hamiltonian connectivity of the WK-recursive network. We use K(d, t) to denote the WK-recursive network of level t, each of which basic modules is a d-vertex complete graph, where d > 1 and t >= 1. The fault-tolerant hamiltonian connectivity H-f(k)(G) is defined to be the maximum integer k such that G is k fault-tolerant hamiltonian connected if G is hamiltonian connected and is undefined otherwise. In this paper, we prove that H-f(k)(K(d, t)) = d - 4 if d >= 4. (C) 2014 Elsevier Inc. All rights reserved.
Fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity of the folded Petersen cube networks
(2009)
Lin, Cheng-Kuan
;
Ho, Tung-Yang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
Some research on the folded Petersen cube networks have been published for the past several years due to its favourite properties. In this paper, we consider the fault-tolerant hamiltonicity and the fault-tolerant hamiltonian connectivity of the folded Petersen cube networks. We use FPQn, k to denote the folded Petersen cube networks of parameters n and k. In this paper, we show that FPQn, k-F remains hamiltonian for any F V(FPQn, k)E(FPQn, k) with |F|n+3k-2 and FPQn, k-F remains hamiltonian connected for any F V(FPQn, k)E(FPQn, k) with |F|n+3k-3 if (n, k){(0, 1)}{(n, 0) | n is a positive integer}. Moreover, this result is optimal.
Fault-Tolerant Hamiltonicity of the WK-Recursive Networks
(2009)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
Many research on the WK-recursive network has been published during the past several years due to its favorite properties. In this paper, we consider the fault-tolerant hamiltonian connectivity of the WK-recursive network. We use K(d,t) to denote the WK-recursive network of level t, each of which basic modules is a d-vertex complete graph. The fault-tolerant hamiltonian connectivity is defined to be the maximum integer k such that G is k fault-tolerant hamiltonian connected if G is hamiltonian connected and is undefined otherwise. In this paper, we prove that the fault-tolerant hamiltonian connectivity of K(d,t) is d-4.
ID-Free Multigroup Cardinality Estimation for Massive RFID Tags in IoT
(2019-01-01)
Lee, Tsu-Kuang
;
Chen, Chih-Chieh
;
Ren, Yi
;
Lin, Cheng-Kuan
;
Tseng, Yu-Chee
The Internet of Things (IoT) has become the hottest in both the research community and industry. Among them, Radio Frequency Identification (RFID) plays a key role in IoT. On the RFID tags estimation problem, most existing researches are trying to identifying tags' ID rather than counting the number of tags. But the number of tags is useful information in many applications such as stock management and traffic flow management. Massive tags cause taking a lot of cost and time in the estimate. So an essential problem is how to quickly and accurately estimate the number of massive tags. In order to solve this problem, this paper proposes an accuracy and efficiency hybrid scheme by decreasing time and space complexity. The results of simulation conducted to test the effectiveness of the proposed approach, which matches well with the theoretical analytical model.
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.
Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs
(2009-07-01)
Chang, Selina Yo-Ping
;
Juan, Justie Su-Tzu
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths P(1) = < u(1), u(2),..., u(v(G))> and P(2) = < v(1), v(2),...,v(v(G))> of G from u to v are independent if u = u(1) = v(1), v = u(v(G)) = v.( G), and u(i) not equal v(i) for every 1 < i < v(G). A set of hamiltonian paths, {P(1), P(2),..., P(k)}, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP( G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n-k >= 2. We use S(n,k) to denote the (n, k)-star graph. In this paper, we prove that IHP(S(n,k)) = n-2 except for S(4,2) such that IHP(S(4,2)) - 1.