Augmentation sous contrainte de diametre Couverture Arbres diametre pair D 2R Arbres diametre impair D 2R Perspectives graphes planaires
57 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
57 pages
Français

Description

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


Sujets

Informations

Publié par
Publié le 01 janvier 2009
Nombre de lectures 37
Langue Français
Poids de l'ouvrage 1 Mo

Exrait

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