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

View/Open

cahier_325.pdf (1.715Mb)

Type

Document de travail / Working paper

Date

2012

Series title

Cahier du LAMSADE

Published in

Paris

Metadata

Show full item record

Author(s)

Boria, Nicolas

Murat, Cécile
Paschos, Vangelis

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 / Keywords

wireless sensor network; Min dominating set