Mixed-weight open locating-dominating sets
Robin M. Givens, Rex K. Kincaid, Weizhen Mao, Gexin Yu · 2017
Wireless sensor networks (WSNs) and other monitoring systems often use sensors of multiple strengths within the same network. This information is lost when the network is modeled by a typical non-weighted graph. We introduce the mixed-weight open locating-dominating set (mixed-weight OLD-set), an extension of the open locating-dominating set, that allows vertices in the graph to have different weights. We show that finding the minimum mixed-weight OLD-set is NP-complete, establish probabilistic bounds for the size of mixed-weight OLD-sets in random graphs, and provide simulation results supporting those bounds.