Browsing by Author "Lin, Wu-Hsiung"

Now showing 1 - 5 of 5

A Suggestion of a New Measure of Importance of Nodes in Disease-propagation Graphs
(2018-01-01)
Liu, Siyu
;
Chen, Chiuyuan
;
Lin, Wu-Hsiung
;
應用數學系
;
Department of Applied Mathematics
One of the most effective ways to protect people from being infected by infectious diseases is through vaccination. However, due to the limitation of vaccine supply, it is usually impractical to vaccinate all of the people in a community. Therefore, how to smartly select a small group of people for targeted vaccination becomes an important issue. Recently, reference [3] deploys a wireless sensor system in a high school in China to collect contacts between students happened within a disease transmission distance. Reference [3] constructs a graph model for disease propagation and presents a measure of importance of nodes, called connectivity centrality, so that targeted vaccination can be performed effectively. We find that although connectivity centrality does provide a nice measure of how a node affects the other nodes during disease propagation, it overemphasizes the contact frequency between nodes and overlooks the number of neighbors of a node. Therefore, in this paper, we suggest a new measure of importance of nodes in disease-propagation graphs. and we show that there exist an infinite number of disease-propagation graphs such that the node selected by our measure is better than that selected by [3].
An Effective Sensor Deployment Scheme that Ensures Multilevel Coverage of Wireless Sensor Networks with Uncertain Properties
(2020-04-01)
Chen, Yu-Ning
;
Lin, Wu-Hsiung
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
The coverage problem is a fundamental problem for almost all applications in wireless sensor networks (WSNs). Many applications even impose the requirement of multilevel (k) coverage of the region of interest (ROI). In this paper, we consider WSNs with uncertain properties. More precisely, we consider WSNs under the probabilistic sensing model, in which the detection probability of a sensor node decays as the distance between the target and the sensor node increases. The difficulty we encountered is that there is no unified definition of k-coverage under the probabilistic sensing model. We overcome this difficulty by proposing a "reasonable" definition of k-coverage under such a model. We propose a sensor deployment scheme that uses less number of deployed sensor nodes while ensuring good coverage qualities so that (i) the resultant WSN is connected and (ii) the detection probability satisfies a predefined threshold p(th), where 0 < p(th) < 1. Our scheme uses a novel "zone 1 and zone 1-2" strategy, where zone 1 and zone 2 are a sensor node's sensing regions that have the highest and the second highest detection probability, respectively, and zone 1-2 is the union of zones 1 and 2. The experimental results demonstrate the effectiveness of our scheme.
Mutual transferability for (F, B, R)-domination on strongly chordal graphs and cactus graphs
(2019-04-30)
Chu, Kuan-Ting
;
Lin, Wu-Hsiung
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
This paper studies a variation of domination in graphs called (F, B, R)-domination. Let G = (V, E) be a graph and V be the disjoint union of F, B, and R, where F consists of free vertices, B consists of bound vertices, and R consists of required vertices. An (F, B, R)-dominating set of G is a subset D subset of V such that R subset of D and each vertex in B - D is adjacent to some vertex in D. An (F, B, R)-2-stable set of G is a subset S subset of B such that S boolean AND N(R) = empty set and every two distinct vertices x and y in S have distance d(x, y) > 2. We prove that if G is strongly chordal, then alpha(F,B,R,2) (G) = gamma(F,B,R)(G)-vertical bar R vertical bar, where gamma(F,B,R)(G) is the minimum cardinality of an (F, B, R)-dominating set of G and alpha(F,B,R,2) (G) is the maximum cardinality of an (F, B, R)-2-stable set of G. Let D-1 ->* D-2 denote D1 being transferable to D-2. We prove that if G is a connected strongly chordal graph in which D-1 and D-2 are two (F, B, R)-dominating sets with vertical bar D-1 vertical bar = vertical bar D-2 vertical bar, then D-1 ->* D-2. We also prove that if G is a cactus graph in which D-1 and D-2 are two (F, B, R) -dominating sets with vertical bar D-1 vertical bar = vertical bar D-2 vertical bar, then D-1 boolean OR {1.extra} ->* D-2 boolean OR{1.extra}, where boolean OR{1.extra} means adding one extra element. (C) 2019 Elsevier B.V. All rights reserved.
Optimal coloring for data collection in tree-based wireless sensor networks
(2017-11-14)
Lo, Shih-Ming
;
Lin, Wu-Hsiung
;
Chen, Chiuyuan
;
Tseng, Yu-Ghee
;
應用數學系
Data collection is an important operation in a wireless sensor network (WSN). During data collection, the interference among nodes cannot be ignored. In a multi-hop WSN, one conventional way of defining interference neighbors is to prohibit a node from using the same time slot as those of its 1-hop and 2-hop neighbors. Recently, it is proved that for data collection in a WSN, since the set of communication nodes is limited and the transmission directions are toward the sink, a less strict set of interference neighbors can be defined [16]. The interference problem in a duty-cycle WSN (DC-WSN) with a corona structure is studied in [7]. In this paper, we solve the same problem by using the relaxed interference set defined in [16]. In particular, we give a complete classification of non-interference sets in 2-hop neighbors. We also propose a distributed 6-coloring algorithm. We prove a lower bound of six colors that every tree-based data collection algorithm requires in a dense DC-WSN, which proves our algorithm to be optimal. (C) 2017 Elsevier B.V. All rights reserved.
THE EQUITABLE CHROMATIC THRESHOLD OF THE CARTESIAN PRODUCT OF BIPARTITE GRAPHS IS AT MOST 4
(2014-06-01)
Yan, Zhidan
;
Lin, Wu-Hsiung
;
Wang, Wei
;
應用數學系
;
Department of Applied Mathematics
A graph G is equitably k-colorable if its vertex set can be partitioned into k independent sets, any two of which differ in size by at most 1. We prove a conjecture of Lin and Chang which asserts that for any bipartite graphs G and H, their Cartesian product G square H is equitably k-colorable whenever k >= 4.