• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail

On the probabilistic min spanning tree Problem

Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2012), On the probabilistic min spanning tree Problem, Journal of Mathematical Modelling and Algorithms, 11, 1, p. 45-76. 10.1007/s10852-011-9165-1

Voir/Ouvrir
cahier306.pdf (388.3Kb)
Type
Article accepté pour publication ou publié
Date
2012
Nom de la revue
Journal of Mathematical Modelling and Algorithms
Volume
11
Numéro
1
Éditeur
Kluwer Academic Publishers
Pages
45-76
Identifiant publication
10.1007/s10852-011-9165-1
Métadonnées
Afficher la notice complète
Auteur(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]
Résumé (EN)
We study a probabilistic optimization model for min spanning tree, where any vertex v i of the input-graph G(V, E) has some presence probability p i in the final instance G′ ⊂ G that will effectively be optimized. Suppose that when this “real” instance G′ becomes known, a spanning tree T, called anticipatory or a priori spanning tree, has already been computed in G and one can run a quick algorithm (quicker than one that recomputes from scratch), called modification strategy, that modifies the anticipatory tree T in order to fit G′. The goal is to compute an anticipatory spanning tree of G such that, its modification for any GG is optimal for G′. This is what we call probabilistic min spanning tree problem. In this paper we study complexity and approximation of probabilistic min spanning tree in complete graphs under two distinct modification strategies leading to different complexity results for the problem. For the first of the strategies developed, we also study two natural subproblems of probabilistic min spanning tree, namely, the probabilistic metric min spanning tree and the probabilistic min spanning tree 1,2 that deal with metric complete graphs and complete graphs with edge-weights either 1, or 2, respectively.
Mots-clés
Spanning tree; Probabilistic optimization; Complexity; Approximation

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    On the probabilistic min spanning tree problem 
    Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2011) Communication / Conférence
  • Vignette de prévisualisation
    The probabilistic minimum dominating set problem 
    Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2018) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Fast Reoptimization for the Minimum Spanning Tree Problem 
    Boria, Nicolas; Paschos, Vangelis (2010) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    An emergency management model for a wireless sensor network problem 
    Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2012) Document de travail / Working paper
  • Vignette de prévisualisation
    A priori optimization for the probabilistic maximum independent set problem 
    Murat, Cécile; Paschos, Vangelis (2002) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo