Property |
Value |
dbo:abstract
|
- 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)
- 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)
|
dbo:namedAfter
| |
dbo:thumbnail
| |
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 8698 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-fr:année
|
- 1970 (xsd:integer)
- 1972 (xsd:integer)
- 2001 (xsd:integer)
|
prop-fr:auteur
|
- Bobby Kleinberg (fr)
- Bobby Kleinberg (fr)
|
prop-fr:doi
| |
prop-fr:isbn
| |
prop-fr:journal
|
- Journal of the ACM (fr)
- Soviet Math. Doklady (fr)
- Journal of the ACM (fr)
- Soviet Math. Doklady (fr)
|
prop-fr:langue
| |
prop-fr:lccn
| |
prop-fr:lieu
|
- Cambridge (fr)
- Cambridge (fr)
|
prop-fr:nom
|
- Stein (fr)
- Edmonds (fr)
- Cormen (fr)
- Dinic (fr)
- Karp (fr)
- Leiserson (fr)
- Rivest (fr)
- Stein (fr)
- Edmonds (fr)
- Cormen (fr)
- Dinic (fr)
- Karp (fr)
- Leiserson (fr)
- Rivest (fr)
|
prop-fr:numéro
| |
prop-fr:numéroChapitre
| |
prop-fr:numéroD'édition
| |
prop-fr:pages
|
- 248 (xsd:integer)
- 1277 (xsd:integer)
|
prop-fr:pagesTotales
| |
prop-fr:passage
| |
prop-fr:prénom
|
- E. A. (fr)
- Richard M. (fr)
- Thomas H. (fr)
- Charles E. (fr)
- Clifford (fr)
- Jack (fr)
- Ronald L. (fr)
- E. A. (fr)
- Richard M. (fr)
- Thomas H. (fr)
- Charles E. (fr)
- Clifford (fr)
- Jack (fr)
- Ronald L. (fr)
|
prop-fr:site
| |
prop-fr:titre
|
- Introduction to Algorithms (fr)
- Theoretical improvements in algorithmic efficiency for network flow problems (fr)
- Algorithm for solution of a problem of maximum flow in a network with power estimation (fr)
- Introduction to Algorithms (fr)
- Theoretical improvements in algorithmic efficiency for network flow problems (fr)
- Algorithm for solution of a problem of maximum flow in a network with power estimation (fr)
|
prop-fr:titreChapitre
|
- Chap. 26 Flows (fr)
- Chap. 26 Flows (fr)
|
prop-fr:url
| |
prop-fr:volume
|
- 11 (xsd:integer)
- 19 (xsd:integer)
|
prop-fr:wikiPageUsesTemplate
| |
prop-fr:wikibooks
|
- en:Algorithm implementation/Graphs/Maximum flow/Edmonds-Karp (fr)
- en:Algorithm implementation/Graphs/Maximum flow/Edmonds-Karp (fr)
|
prop-fr:wikibooksTitre
|
- Algorithme d'Edmonds-Karp (fr)
- Algorithme d'Edmonds-Karp (fr)
|
prop-fr:éditeur
|
- Association for Computing Machinery (fr)
- Doklady Nauk SSSR (fr)
- MIT Press and McGraw-Hill (fr)
- Association for Computing Machinery (fr)
- Doklady Nauk SSSR (fr)
- MIT Press and McGraw-Hill (fr)
|
dct:subject
| |
rdf:type
| |
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)
- 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)
|
rdfs:label
|
- Algorithme d'Edmonds-Karp (fr)
- Edmonds–Karp algorithm (en)
- Thuật toán Edmonds–Karp (vi)
- Алгоритм Едмондса — Карпа (uk)
- Алгоритм Эдмондса — Карпа (ru)
- エドモンズ・カープのアルゴリズム (ja)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:depiction
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageDisambiguates
of | |
is dbo:wikiPageRedirects
of | |
is dbo:wikiPageWikiLink
of | |
is oa:hasTarget
of | |
is foaf:primaryTopic
of | |