The probabilistic minimum dominating set problem
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2018), The probabilistic minimum dominating set problem, Discrete Applied Mathematics, 234, p. 93-113. 10.1016/j.dam.2016.10.016
Type
Article accepté pour publication ou publiéDate
2018Journal name
Discrete Applied MathematicsNumber
234Publisher
Elsevier
Pages
93-113
Publication identifier
Metadata
Show full item recordAuthor(s)
Boria, Nicolas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Murat, Cécile
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We present a natural wireless sensor network problem, which we model as a probabilistic version of the min dominating set problem (called probabilistic min dominating set). We first show that calculation of the objective function of this general probabilistic problem is -complete. We then introduce a restricted version of probabilistic min dominating set and show that, this time, calculation of its objective function can be performed in polynomial time and that this restricted problem is “just” NP-hard, since it is a generalization of the classical min dominating set. We study the complexity of this restricted version in graphs where min dominating set is polynomial, mainly in trees and paths and then we give some approximation results for it.Subjects / Keywords
Complexity; Approximation; Probabilistic optimization; Dominating set; Wireless sensor networksRelated items
Showing items related by title and author.
-
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2011) Communication / Conférence
-
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2012) Article accepté pour publication ou publié
-
Paschos, Vangelis; Murat, Cécile (2002) Article accepté pour publication ou publié
-
Murat, Cécile; Paschos, Vangelis (2002) Article accepté pour publication ou publié
-
Murat, Cécile; Paschos, Vangelis (1995) Communication / Conférence