About: Push–relabel maximum flow algorithm

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Push–relabel maximum flow algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : wikidata:Q8366, within Data Space : prod-dbpedia.inria.fr associated with source document(s)

Attributes	Values
rdf:type	Thing Algorithm Algorithm
rdfs:label	Algorithme de poussage/réétiquetage (fr) Push–relabel maximum flow algorithm (en) Алгоритм проталкивания предпотока (ru)
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)
sameAs	Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm Push–relabel maximum flow algorithm
Wikipage page ID	7828034 (xsd:integer)
Wikipage revision ID	177026727 (xsd:integer)
dbo:wikiPageWikiLink	category-fr:Réseau_de_flot Edmonds–Karp algorithm category-fr:Algorithme_de_la_théorie_des_graphes Time complexity dbpedia-fr:Lois_de_Kirchhoff dbpedia-fr:Problème_de_flot_maximum Robert Tarjan dbpedia-fr:Réseau_de_flot Max-flow min-cut theorem
page length (characters) of wiki page	14266 (xsd:nonNegativeInteger)
dct:subject	category-fr:Réseau_de_flot category-fr:Algorithme_de_la_théorie_des_graphes
prop-fr:wikiPageUsesTemplate	dbpedia-fr:Modèle:' dbpedia-fr:Modèle:2e dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:Lien dbpedia-fr:Modèle:Ouvrage dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Traduction/Référence
prov:wasDerivedFrom	wikipedia-fr:Algorithme_de_poussage/réétiquetage?oldid=177026727&ns=0
foaf:depiction
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)
prop-fr:doi	10 (xsd:double)
prop-fr:isbn	0 (xsd:integer) 978 (xsd:integer)
prop-fr:journal	Proceedings of the eighteenth annual ACM symposium on Theory of computing (fr)
prop-fr:langue	en (fr) fr (fr)
prop-fr:lieu	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)
prop-fr:pages	136 (xsd:integer)
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)
prop-fr:responsabilité	auteurs (fr) traducteurs (fr)
prop-fr:sousTitre	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)
prop-fr:titreChapitre	8 (xsd:double) 8 (xsd:double) Chap. 26 Flows (fr)
prop-fr:éditeur	Springer (fr) MIT Press and McGraw-Hill (fr) Springer-France (fr)
prop-fr:numéroD'édition	2 (xsd:integer)

Faceted Search & Find service v1.16.111 as of Oct 19 2022

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 5 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software