Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

De
57 pages
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


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

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin