SERVICE DE LA DOCUMENTATION ET DES ARCHIVES DE LA FST
Accueil
(1996)
| Titre : |
Algorithmes de recherche d'un flot maximum dans un réseau |
| Type de document : |
texte imprimé |
| Auteurs : |
Christian Volland, Auteur |
| Editeur : |
Université Cheikh Anta Diop de Dakar : Faculté des Sciences et Techniques : Département de Mathématiques-Informatique |
| Année de publication : |
1996 |
| Importance : |
64 P. |
| Format : |
29 cm |
| Langues : |
Français (fre) |
| Mots-clés : |
algorithme Algorithme de recherche Flot maximum Reseau |
| Résumé : |
L'objectif de ce travail est la présentation et l'étude de quelques uns des
principaux algorithmes déterminant un flot maximum dans un réseau.
La première partie est consacrée au problème de la recherche d'un chemin entre
deux sommets, en "profondeur" ou en "largeur". Ensuite, nous présentons la méthode
de Ford et Fulkerson (1956), et, en particulier, une variante de cette méthode que l'on
doit à Edmonds et Ka11'· L'algorithme obtenu a une complexité d'ordre O(n m2; dans
un réseau ayant n sommets et m arcs.
Les deux algorithmes suivants sont celui de Dinic ( 1970) et celui de Mfalhotra,
Pramodh Kumar et Maheshwari (1978), dont les complexités sont, respectivement,
d'ordre O(n2 m) et O(n3).
La dernière méthode exposée fait intervenir la notion de pré-flot. Nous avons
détaillé les algorithmes "FIFO" (Goldberg) et "d'élévation vers l'avant" qui ont une
complexjté en O(n3). Il s'agit d'exemples parmi les algorithmes du type "push-relabel". |
| Permalink : |
https://bibliothequefst.ucad.sn/index.php?lvl=notice_display&id=1577 |
Algorithmes de recherche d'un flot maximum dans un réseau [texte imprimé] / Christian Volland, Auteur . - Université Cheikh Anta Diop de Dakar : Faculté des Sciences et Techniques : Département de Mathématiques-Informatique, 1996 . - 64 P. ; 29 cm. Langues : Français ( fre)
| Mots-clés : |
algorithme Algorithme de recherche Flot maximum Reseau |
| Résumé : |
L'objectif de ce travail est la présentation et l'étude de quelques uns des
principaux algorithmes déterminant un flot maximum dans un réseau.
La première partie est consacrée au problème de la recherche d'un chemin entre
deux sommets, en "profondeur" ou en "largeur". Ensuite, nous présentons la méthode
de Ford et Fulkerson (1956), et, en particulier, une variante de cette méthode que l'on
doit à Edmonds et Ka11'· L'algorithme obtenu a une complexité d'ordre O(n m2; dans
un réseau ayant n sommets et m arcs.
Les deux algorithmes suivants sont celui de Dinic ( 1970) et celui de Mfalhotra,
Pramodh Kumar et Maheshwari (1978), dont les complexités sont, respectivement,
d'ordre O(n2 m) et O(n3).
La dernière méthode exposée fait intervenir la notion de pré-flot. Nous avons
détaillé les algorithmes "FIFO" (Goldberg) et "d'élévation vers l'avant" qui ont une
complexjté en O(n3). Il s'agit d'exemples parmi les algorithmes du type "push-relabel". |
| Permalink : |
https://bibliothequefst.ucad.sn/index.php?lvl=notice_display&id=1577 |
|  |
Réservation
Réserver ce document
Exemplaires(3)
|
MEM 894
|
MEM 894 |
Mémoire de DEA |
Master mathématiques et Informatique |
Informatique
|
Disponible |
|
MEM 895
|
MEM 895 |
Mémoire de DEA |
Master mathématiques et Informatique |
Informatique
|
Disponible |
|
MEM 896
|
MEM 896 |
Mémoire de DEA |
Master mathématiques et Informatique |
Informatique
|
Disponible |
