An emergency management model for a wireless sensor network problem

Boria, Nicolas; Murat, Cécile; Paschos, Vangelis

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

Voir/Ouvrir

cahier_325.pdf (1.715Mb)

Type

Document de travail / Working paper

Date

2012

Titre de la collection

Cahier du LAMSADE

Ville d’édition

Paris

Métadonnées

Afficher la notice complète

Auteur(s)

Boria, Nicolas

Murat, Cécile
Paschos, Vangelis

Résumé (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.