About: Edmonds–Karp algorithm

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

About: Edmonds–Karp 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 d'Edmonds-Karp (fr) Edmonds–Karp algorithm (en) Thuật toán Edmonds–Karp (vi) Алгоритм Едмондса — Карпа (uk) Алгоритм Эдмондса — Карпа (ru) エドモンズ・カープのアルゴリズム (ja)
rdfs:comment	En informatique et en théorie des graphes, l'algorithme d'Edmonds–Karp (ou algorithme d'Edmonds et Karp) est une spécialisation de l'algorithme de Ford-Fulkerson de résolution du problème de flot maximum dans un réseau, en temps O(V E2). Il est asymptotiquement plus lent que l'algorithme de poussage/reétiquetage qui utilise une heuristique basée sur une pile et qui est en temps O(V3), mais il est souvent plus rapide en pratique pour des graphes denses. L'algorithme a été publié d'abord par Yefim (Chaim) Dinic en 1970 puis et indépendamment par Jack Edmonds et Richard Karp en 1972. L'algorithme de Dinic contient un critère de sélection supplémentaire qui réduit le temps de calcul à O(V2 E). (fr)
sameAs	Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm Edmonds–Karp algorithm
Wikipage page ID	7815697 (xsd:integer)
Wikipage revision ID	178662119 (xsd:integer)
dbo:wikiPageWikiLink	category-fr:Réseau_de_flot Dinic's algorithm Ford–Fulkerson algorithm Breadth-first search Push–relabel maximum flow algorithm category-fr:Algorithme_de_la_théorie_des_graphes Big O notation Time complexity dbpedia-fr:Coupe_minimum dbpedia-fr:Densité_d'un_graphe Herbert Wilf Computer science dbpedia-fr:Jack_Edmonds dbpedia-fr:Problème_de_flot_maximum dbpedia-fr:Problème_de_plus_court_chemin Richard M. Karp dbpedia-fr:Théorie_des_graphes Max-flow min-cut theorem Cornell University
Link from a Wikipage to an external page	http://www.cs.cornell.edu/courses/cs4820/2012su/handouts/edmondskarp.pdf%7Ctitre=Edmonds-Karp http://www.cs.bgu.ac.il/~dinitz/D70.pdf https://web.archive.org/web/20061005083406/http:/www.cis.upenn.edu/~wilf/AlgComp3.html
page length (characters) of wiki page	8698 (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:3 dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:Autres_projets dbpedia-fr:Modèle:Lien_web 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 dbpedia-fr:Modèle:Voir_homonymes dbpedia-fr:Modèle:2 dbpedia-fr:Modèle:Boîte_déroulante/début dbpedia-fr:Modèle:Boîte_déroulante/fin
prov:wasDerivedFrom	wikipedia-fr:Algorithme_d'Edmonds-Karp?oldid=178662119&ns=0
foaf:depiction
prop-fr:année	1970 (xsd:integer) 1972 (xsd:integer) 2001 (xsd:integer)
prop-fr:auteur	Bobby Kleinberg (fr)
prop-fr:doi	10 (xsd:double)
prop-fr:isbn	978 (xsd:integer)
prop-fr:journal	Journal of the ACM (fr) Soviet Math. Doklady (fr)
prop-fr:langue	en (fr)
prop-fr:lieu	Cambridge (fr)
prop-fr:nom	Stein (fr) Edmonds (fr) Cormen (fr) Dinic (fr) Karp (fr) Leiserson (fr) Rivest (fr)
prop-fr:numéro	2 (xsd:integer)
prop-fr:pages	248 (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, 13 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software