Browsing by Author "Jia, Xiaohua"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
Item Maximal Independent Set and Minimum Connected Dominating Set in Unit Disk Graphs(2004-12-13) WuLi, Wei; Du, Hongwei; Jia, Xiaohua; Li, Yingshu; Huang, Scott C.-H.; Du, Ding-ZhuIn ad hoc wireless networks, the connected dominating set can be used as a virtual backbone to improve the performance. Many constructions for approximating the minimum connected dominating set are based on construction of maximal independent set. The relation between the size mis(G) of a maximum independent set and the size cds(G) of minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Previously, it is known that mis(G)<=4*cds(G)+1 for all unit disk graph G. In this paper, we improve it by showing mis(G)<=3.8*cds(G)+1.2.Item Optimal Consecutive-k-out-of-n: G Cycle for n <= 2k+1(2000-10-02) Du, Ding-Zhu; Hwang, Frank K.; Jia, Xiaohua; Ngo, Hung Q.We present a complete proof for the invariant optimal assignment for consecutive-k-out-of-n: G Cycle for k , which was proposed by Zuo and Kao in 1990 with an incomplete proof, pointed out recently by Jalali, Hawkes, Cui, and Hwang.Item Rivest-Vuillemin Conjecture Is True for Monotone Boolean Functions with Twelve Variables(2000-10-02) Gao, Sui-xiang; Du, Ding-Zhu; Hu, Xiao-dong; Jia, XiaohuaA Boolean function f(x1, x2, …, xn) is elusive if every decision tree computing f must examine all n variables in the worst case. It is a long-standing conjecture that every non-trivial monotone weakly symmetric Boolean function is elusive. In this paper, we prove this conjecture for Boolean functions with twelve variables.Item Wireless Sensor Networks with Energy Efficient Organization(2002-12-08) Cardei, Mihaela; MacCallum, David; Cheng, Xiaoyan; Min, Manki; Jia, Xiaohua; Li, Deying; Du, Ding-Zhu; Hung-Chang Du, DavidA critical aspect of applications with wireless sensor networks is network lifetime. Battery-powered sensors are usable as long as they can communicate captured data to a processing node. Sensing and communications consume energy, therefore judicious power management and scheduling caneffectively extend the operational time. One important class of wireless sensor applications consists of deployment of large number of sensors in an area for environmental monitoring. The data collected by the sensors is sent to a central node for processing. In this paper we propose an efficient method to achieve energy savings by organizing the sensor nodes into a maximum number of disjoint dominating sets (DDS) which are activated successively. Only the sensors from the active set are responsible for monitoring the target area and for disseminating the collected data. All other nodes are into a sleep mode, characterized by a low energy consumption. We define the maximum disjoint dominating sets problem and we design a heuristic that computes the sets. Theoretical analysis and performance evaluation results are presented to verify our approach.