Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

Augmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Augmentation de graphe sous contrainte de
diam`etre
V. Chepoi, B. Estellon, K. Nouioua, Y. Vax`es
Universit´e de la M´editerran´ee
Laboratoire d’Informatique Fondamentale de Marseille
´Equipe Combinatoire et Recherche Op´erationnelle
23 janvier 2009Augmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Plan
1 Augmentation sous contrainte de diam`etre
2 Couverture
3 Arbres : diam`etre pair D = 2R
4 Arbres : diam`etre impair D = 2R +1
5 Perspectives : graphes planaires, ...Augmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Introduction
Domaine de recherche
Probl`emes algorithmiques li´es aux distances dans les graphes
Diam`etre
Quel est la distance maximum entre deux
u sommets?
Borner le d´elai maximum de communications
v
Probl´ematique
Classe complexit´e des probl`emes rencontr´es
Pbs NP-difficiles : algorithmes d’approximation
Classes de graphesAugmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Introduction
Domaine de recherche
Probl`emes algorithmiques li´es aux distances dans les graphes
Augmentation
Combien d’arˆetes faudrait-il ajouter pour
obtenir un graphe de diam`etre donn´e?u
Am´eliorer un r´eseau en ajoutant des liaisons.
v
Probl´ematique
Classe complexit´e des probl`emes rencontr´es
Pbs NP-difficiles : algorithmes d’approximation
Classes de graphesAugmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Introduction
Domaine de recherche
Probl`emes algorithmiques li´es aux distances dans les graphes
Augmentation
Combien d’arˆetes faudrait-il ajouter pour
obtenir un graphe de diam`etre donn´e?u
Am´eliorer un r´eseau en ajoutant des liaisons.
v
Probl´ematique
Classe complexit´e des probl`emes rencontr´es
Pbs NP-difficiles : algorithmes d’approximation
Classes de graphesAugmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Notions
Algorithme d’approximation
Un algorithme d’approximation avec un facteur α pour un probl`eme de
minimisation Π est un algorithme polynomial, pour chaque instance I de
Π, d´elivre une solution dont le couˆt est au plus α fois OPT (I).Π
Notions li´ees aux distances dans les graphes
la distance d (u,v) entre deux sommets u et v est le nombreG
minimum d’arˆetes dans un chemin entre u et v ;
le diam`etre du graphe G, diam(G) = max{d (u,v) :u,v ∈V}G
la boule de rayon R centr´ee en v, B (v) ={u∈V :d (u,v)≤R}R GAugmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Deux probl`emes sur les graphes :
Couverture d’un graphe par des boules.
Augmentation sous contraintes de diam`etre.
Couverture
Augmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Deux probl`emes sur les graphes :
Couverture d’un graphe par des boules.
Augmentation sous contraintes de diam`etre.
Couverture
Augmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Deux probl`emes sur les graphes :
Couverture d’un graphe par des boules.
Augmentation sous contraintes de diam`etre.
Couverture Augmentation
Augmentation sous contrainte de diam`etre Couverture Arbres : diam`etre pair D = 2R Arbres : diam`etre impair D = 2R + 1 Perspectives : graphes planaires,
Deux probl`emes sur les graphes :
Couverture d’un graphe par des boules.
Augmentation sous contraintes de diam`etre.
Couverture Augmentation