An emergency management model for a wireless sensor network problem
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2012), An emergency management model for a wireless sensor network problem. https://basepub.dauphine.fr/handle/123456789/10608
TypeDocument de travail / Working paper
Series titleCahier du LAMSADE
MetadataShow full item record
Abstract (EN)We present a natural wireless sensor network problem, which we model as a probabilisticversion of the min dominating set problem. We show that this problem, being a generalization of the classical min dominating set, is NP-hard, even in bipartite graphs. We firststudy the complexity of probabilistic min dominating set in graphs where min dominatingset is polynomial, mainly in trees and paths and then we give some approximationresults for it.
Subjects / Keywordswireless sensor network; Min dominating set
Showing items related by title and author.