This HTML5 document contains 106 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
n26http://fr.dbpedia.org/resource/Théorème_flot-max/
dbohttp://dbpedia.org/ontology/
n2http://fr.dbpedia.org/resource/Algorithme_de_poussage/
foafhttp://xmlns.com/foaf/0.1/
n27http://g.co/kg/m/
dbpedia-ruhttp://ru.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-srhttp://sr.dbpedia.org/resource/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-plhttp://pl.dbpedia.org/resource/
n16http://fr.dbpedia.org/resource/Modèle:
dbpedia-cshttp://cs.dbpedia.org/resource/
n7http://fr.dbpedia.org/resource/Fichier:
n13http://fr.dbpedia.org/resource/Modèle:Traduction/
n15http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n14http://ma-graph.org/entity/
n24http://fr.wikipedia.org/wiki/Algorithme_de_poussage/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
dbpedia-thhttp://th.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
n2:réétiquetage
rdf:type
dbo:Algorithm wikidata:Q8366 owl:Thing
rdfs:label
Push–relabel maximum flow algorithm Алгоритм проталкивания предпотока Algorithme de poussage/réétiquetage
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
owl:sameAs
dbpedia-cs:Goldbergův_algoritmus wikidata:Q583889 n14:28977562 dbpedia-de:Goldberg-Tarjan-Algorithmus dbpedia-fa:الگوریتم_ارسال-برچسب dbr:Push–relabel_maximum_flow_algorithm dbpedia-th:ขั้นตอนวิธีการผลักดัน_-_ติดป้ายใหม่ dbpedia-ru:Алгоритм_проталкивания_предпотока dbpedia-sr:Push-relabel_algoritam_maksimalnog_protoka_grafa n27:09cr90 dbpedia-pl:Algorytm_push-relabel
dbo:wikiPageID
7828034
dbo:wikiPageRevisionID
177026727
dbo:wikiPageWikiLink
dbpedia-fr:Robert_Tarjan dbpedia-fr:Algorithme_d'Edmonds-Karp n7:Network_flow_residual_SVG.svg n7:Network_flow.png dbpedia-fr:Lois_de_Kirchhoff category-fr:Algorithme_de_la_théorie_des_graphes category-fr:Réseau_de_flot dbpedia-fr:Réseau_de_flot dbpedia-fr:Complexité_en_temps dbpedia-fr:Problème_de_flot_maximum n26:coupe-min
dbo:wikiPageLength
14266
dct:subject
category-fr:Réseau_de_flot category-fr:Algorithme_de_la_théorie_des_graphes
prop-fr:wikiPageUsesTemplate
n13:Référence n16:Article n16:' n16:Lien n16:2e n16:Ouvrage n16:Références n16:Portail
prov:wasDerivedFrom
n24:réétiquetage?oldid=177026727&ns=0
foaf:depiction
n15:Network_flow.png n15:Network_flow_residual_SVG.svg
prop-fr:année
2001 2010 2008 1986
prop-fr:collection
IRIS Algorithms and Combinatorics
prop-fr:doi
10.1145
prop-fr:isbn
0 978
prop-fr:journal
Proceedings of the eighteenth annual ACM symposium on Theory of computing
prop-fr:langue
fr en
prop-fr:lieu
Cambridge
prop-fr:nom
Vygen Tarjan Skoda Stein Fonlupt Cormen Korte Goldberg Leiserson Rivest
prop-fr:pages
136
prop-fr:pagesTotales
1180 627
prop-fr:passage
643 174 182
prop-fr:prénom
Bernard H. Charles E. Clifford Jens Alexandre Ronald L. Thomas H. Andrew V. Jean Bernard Robert E.
prop-fr:responsabilité
auteurs traducteurs
prop-fr:sousTitre
théorie et algorithmes Theory and Algorithms
prop-fr:titre
Optimisation combinatoire Combinatorial Optimization A new approach to the maximum flow problem Introduction to Algorithms
prop-fr:titreChapitre
Chap. 26 Flows 8.5 8.4
prop-fr:éditeur
Springer-France MIT Press and McGraw-Hill Springer
prop-fr:numéroD'édition
2
prop-fr:lccn
2001031277
prop-fr:numéroChapitre
26
prop-fr:numéroDansCollection
21
dbo:thumbnail
n15:Network_flow.png?width=300
foaf:isPrimaryTopicOf
n24:réétiquetage
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.