| Property |
Value |
| dbo:abstract
|
- L'algorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986. L'algorithme général a une complexité en temps en (ici est l'ensemble des sommets, et l'ensemble des arcs du graphe) ; une implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en ; une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité . Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un (en) donne un temps d'exécution majoré par . Tous ces temps sont meilleurs que la majoration en qui est celle de l'algorithme d'Edmonds-Karp. (fr)
- L'algorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986. L'algorithme général a une complexité en temps en (ici est l'ensemble des sommets, et l'ensemble des arcs du graphe) ; une implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en ; une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité . Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un (en) donne un temps d'exécution majoré par . Tous ces temps sont meilleurs que la majoration en qui est celle de l'algorithme d'Edmonds-Karp. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 14266 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1986 (xsd:integer)
- 2001 (xsd:integer)
- 2008 (xsd:integer)
- 2010 (xsd:integer)
|
| prop-fr:collection
|
- Algorithms and Combinatorics (fr)
- IRIS (fr)
- Algorithms and Combinatorics (fr)
- IRIS (fr)
|
| prop-fr:doi
| |
| prop-fr:isbn
|
- 0 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:journal
|
- Proceedings of the eighteenth annual ACM symposium on Theory of computing (fr)
- Proceedings of the eighteenth annual ACM symposium on Theory of computing (fr)
|
| prop-fr:langue
|
- en (fr)
- fr (fr)
- en (fr)
- fr (fr)
|
| prop-fr:lccn
| |
| prop-fr:lieu
|
- Cambridge (fr)
- Cambridge (fr)
|
| prop-fr:nom
|
- Stein (fr)
- Korte (fr)
- Goldberg (fr)
- Cormen (fr)
- Fonlupt (fr)
- Leiserson (fr)
- Rivest (fr)
- Skoda (fr)
- Tarjan (fr)
- Vygen (fr)
- Stein (fr)
- Korte (fr)
- Goldberg (fr)
- Cormen (fr)
- Fonlupt (fr)
- Leiserson (fr)
- Rivest (fr)
- Skoda (fr)
- Tarjan (fr)
- Vygen (fr)
|
| prop-fr:numéroChapitre
| |
| prop-fr:numéroD'édition
| |
| prop-fr:numéroDansCollection
| |
| prop-fr:pages
| |
| prop-fr:pagesTotales
|
- 627 (xsd:integer)
- 1180 (xsd:integer)
|
| prop-fr:passage
|
- 174 (xsd:integer)
- 182 (xsd:integer)
- 643 (xsd:integer)
|
| prop-fr:prénom
|
- Jean (fr)
- Jens (fr)
- Alexandre (fr)
- Bernard (fr)
- Thomas H. (fr)
- Charles E. (fr)
- Clifford (fr)
- Robert E. (fr)
- Andrew V. (fr)
- Bernard H. (fr)
- Ronald L. (fr)
- Jean (fr)
- Jens (fr)
- Alexandre (fr)
- Bernard (fr)
- Thomas H. (fr)
- Charles E. (fr)
- Clifford (fr)
- Robert E. (fr)
- Andrew V. (fr)
- Bernard H. (fr)
- Ronald L. (fr)
|
| prop-fr:responsabilité
|
- auteurs (fr)
- traducteurs (fr)
- auteurs (fr)
- traducteurs (fr)
|
| prop-fr:sousTitre
|
- Theory and Algorithms (fr)
- théorie et algorithmes (fr)
- Theory and Algorithms (fr)
- théorie et algorithmes (fr)
|
| prop-fr:titre
|
- Optimisation combinatoire (fr)
- Combinatorial Optimization (fr)
- A new approach to the maximum flow problem (fr)
- Introduction to Algorithms (fr)
- Optimisation combinatoire (fr)
- Combinatorial Optimization (fr)
- A new approach to the maximum flow problem (fr)
- Introduction to Algorithms (fr)
|
| prop-fr:titreChapitre
|
- 8.400000 (xsd:double)
- 8.500000 (xsd:double)
- Chap. 26 Flows (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Springer (fr)
- MIT Press and McGraw-Hill (fr)
- Springer-France (fr)
- Springer (fr)
- MIT Press and McGraw-Hill (fr)
- Springer-France (fr)
|
| dct:subject
| |
| rdf:type
| |
| rdfs:comment
|
- L'algorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986. L'algorithme général a une complexité en temps en (ici est l'ensemble des sommets, et l'ensemble des arcs du graphe) ; une implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en ; une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité . Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un (fr)
- L'algorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986. L'algorithme général a une complexité en temps en (ici est l'ensemble des sommets, et l'ensemble des arcs du graphe) ; une implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en ; une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité . Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un (fr)
|
| rdfs:label
|
- Algorithme de poussage/réétiquetage (fr)
- Push–relabel maximum flow algorithm (en)
- Алгоритм проталкивания предпотока (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
