Augmentation sous contrainte de diametre Couverture Arbres diametre pair D 2R Arbres diametre impair D 2R Perspectives graphes planaires

De
Publié par

Augmentation sous contrainte de diametre Couverture Arbres : diametre pair D = 2R Arbres : diametre impair D = 2R + 1 Perspectives : graphes planaires, Augmentation de graphe sous contrainte de diametre V. Chepoi, B. Estellon, K. Nouioua, Y. Vaxes Universite de la Mediterranee Laboratoire d'Informatique Fondamentale de Marseille Equipe Combinatoire et Recherche Operationnelle 23 janvier 2009

  • delai maximum de communications

  • problemes algorithmiques

  • classe complexite des problemes

  • diametre pair

  • lies aux distances dans les graphes

  • graphe planaire

  • laboratoire d'informatique fondamentale


Publié le : jeudi 1 janvier 2009
Lecture(s) : 43
Tags :
Source : lirmm.fr
Nombre de pages : 57
Voir plus Voir moins

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

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.