Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Randomized Algorithms For Approximating A Connected Dominating Set In Wireless Sensor Networks, Akshaye Dhawan, Michelle Tanco, Aaron Yeiser
Randomized Algorithms For Approximating A Connected Dominating Set In Wireless Sensor Networks, Akshaye Dhawan, Michelle Tanco, Aaron Yeiser
Mathematics and Computer Science Faculty Publications
A Connected Dominating Set (CDS) of a graph representing a Wireless Sensor Network can be used as a virtual backbone for routing through the network. Since the sensors in the network are constrained by limited battery life, we desire a minimal CDS for the network, a known NP-hard problem. In this paper we present three randomized algorithms for constructing a CDS. We evaluate our algorithms using simulations and compare them to the two-hop K2 algorithm and two other greedy algorithms from the literature. After pruning, the randomized algorithms construct a CDS that are generally equivalent in size to those constructed …
Positive Influence Dominating Set Generation In Social Networks, Akshaye Dhawan, Matthew Rink
Positive Influence Dominating Set Generation In Social Networks, Akshaye Dhawan, Matthew Rink
Mathematics and Computer Science Faculty Publications
Current algorithms in the Positive Influence Dominating Set (PIDS) problem domain are focused on a specific type of PIDS, the Total Positive Influence Dominating Set (TPIDS). We have developed an algorithm specifically targeted towards the non-total type of PIDS. In addition to our new algorithm, we adapted two existing TPIDS algorithms to generate PIDS. We ran simulations for all three algorithms, and our new algorithm consistently generates smaller PIDS than both existing algorithms, with our algorithm generating PIDS approximately 5% smaller than the better of the two existing algorithms.