• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2018
Journal name
Discrete Applied Mathematics
Number
234
Publisher
Elsevier
Pages
93-113
Publication identifier
10.1016/j.dam.2016.10.016
Metadata
Show full item record
Author(s)
Boria, Nicolas cc
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 networks

Related items

Showing items related by title and author.

  • Thumbnail
    On the probabilistic min spanning tree problem 
    Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2011) Communication / Conférence
  • Thumbnail
    On the probabilistic min spanning tree Problem 
    Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2012) Article accepté pour publication ou publié
  • Thumbnail
    The probabilistic minimum vertex covering problem 
    Paschos, Vangelis; Murat, Cécile (2002) Article accepté pour publication ou publié
  • Thumbnail
    A priori optimization for the probabilistic maximum independent set problem 
    Murat, Cécile; Paschos, Vangelis (2002) Article accepté pour publication ou publié
  • Thumbnail
    The probabilistic maximum independent set problem 
    Murat, Cécile; Paschos, Vangelis (1995) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo