In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in time. The algorithm was first published by Yefim Dinitz (whose name is also transliterated "E. A. Dinic", notably as author of his early papers) in 1970 and independently published by Jack Edmonds and Richard Karp in 1972. Dinic's algorithm includes additional techniques that reduce the running time to . The Wikibook Algorithm implementation has a page on the topic of: Edmonds-Karp
| Attributes | Values |
|---|
| type
| |
| sameAs
| |
| wasDerivedFrom
| |
| dbpedia-owl:abstract
| - 计算机科学中，埃德蒙兹-卡普算法通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为。该算法由叶菲姆·迪尼茨在1970年最先提出，并由杰克·埃德蒙兹和在1972年独立发表。
- エドモンズ・カープのアルゴリズム（英: Edmonds-Karp algorithm）は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、 の計算量である。 のに比べると漸近的に遅いが、（辺の少ない）疎なグラフでは速い。このアルゴリズムは1970年にロシア人科学者 Dinic が発表し、それとは独立に1972年にとリチャード・カープが発表した（発見はこちらの方が早かった）。Dinic のアルゴリズムには追加の技法が含まれており、計算量は となっている。
- 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).
- Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время в графе . Впервые был опубликован в 1970 году советским учёным . Позже, в 1972 году, был независимо открыт Эдмондсом и Карпом.
- In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in time. The algorithm was first published by Yefim Dinitz (whose name is also transliterated "E. A. Dinic", notably as author of his early papers) in 1970 and independently published by Jack Edmonds and Richard Karp in 1972. Dinic's algorithm includes additional techniques that reduce the running time to . The Wikibook Algorithm implementation has a page on the topic of: Edmonds-Karp
- Algorytm Edmondsa-Karpa jest jedną z realizacji metody Forda-Fulkersona rozwiązywania problemu maksymalnego przepływu w sieci przepływowej. Jego złożoność czasowa wynosi jest zatem wolniejszy od innych znanych algorytmów przepływowych działających w czasie takich jak algorytm relabel-to-front, czy . W praktyce jednak złożoność pesymistyczna rzadko jest osiągana, co w połączeniu z prostotą czyni algorytm Edmondsa-Karpa bardzo użytecznym, szczególnie dla grafów rzadkich. Algorytm ten został odkryty przez rosyjskiego naukowca, w roku 1970, i niezależnie przez i Richarda Karpa w roku 1972. Artykuł Dinica zawiera dodatkowe techniki, które obniżają czas działania do (algorytm z tą poprawką nazywa się obecnie algorytmem Dynica).
- Edmondsův-Karpův algoritmus je v informatice a teorii grafů implementací Fordovy-Fulkersonovy metody pro výpočet maximálního toku v síti s časovou složitostí . Je asymptoticky pomalejší než Goldbergův algoritmus s časovou složitostí , ale v praxi je rychlejší pro . Dinic, ruský vědec, publikoval algoritmus poprvé v roce 1970 nezávisle na publikování stejného algoritmu Kanaďanem a Američanem Richardem Karpem v roce 1972 (údajně objeven dříve). Dinicův algoritmus obsahuje navíc techniky, které redukují časovou složitost na .
- En informàtica i teoria de grafs, l'algorisme d'Edmonds–Karp és una especificació del de per calcular el flux màxim en una xarxa de flux amb cost . Aquest és assimpdòticament més lent que que té un cost de , però pot ser més ràpid en grafs dispersos. L'algorisme va ser publicat primer per un científic rus, Yefim (Chaim) Dinic, l'any 1970, i independentment per Jack Edmonds i Richard Karp el 1972 (però descobert abans). L'algorisme de Dinic inclou tècniques addicionals per reduir el temps d'execució a .
- Der Edmonds-Karp-Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung des Ford-Fulkerson-Algorithmus zur Berechnung des maximalen s-t-Flusses in Netzwerken mit positiven reellen Kapazitäten. Sie verwendet den jeweils kürzesten augmentierenden Pfad in jedem Schritt, was sicherstellt, dass der Algorithmus in polynomieller Zeit terminiert. In den meisten Implementierungen wird der kürzeste Pfad durch eine Breitensuche ermittelt, was zu einer Laufzeit in führt. Der Algorithmus wurde zuerst 1970 von dem russischen Wissenschaftler publiziert und später unabhängig von Jack Edmonds und Richard M. Karp, die ihn 1972 publizierten, entdeckt. Dinics Algorithmus enthält zusätzliche Techniken zur Reduzierung der Laufzeit auf .
- En ciencias de la computación y teoría de grafos, el Algoritmo de Edmonds-Karp es una implementación del método de Ford-Fulkerson para calcular el flujo maximal en una red de flujo(i.e. computer network) con complejidad O(V E2). Es asintóticamente más lento que el , que tiene complejidad O(V3), pero es habitualmente más rápido en la práctica para grafos ralos. El algoritmo fue publicado por primera vez por un científico soviético, Yefim (Chaim) Dinic, en 1970, e independientemente por Jack Edmonds y Richard Karp en 1972. El Algoritmo de Dinic incluye técnicas adicionales para reducir la complejidad a O(V2E).
- Алгоритм Едмондса — Карпа розв'язує задачу знаходження максимального потоку в транспортній мережі. Алгоритм являє собою окремий випадок методу Форда-Фалкерсона і працює за час . Вперше був опублікований в 1970 році радянським вченим Ю. А. Деніцом. Пізніше, в 1972 році, був незалежно відкритий Едмондсом і Карпом. Алгоритм Дініца подає додаткові підходи для зменшення часу до .
- Na Ciência da computação e teoria dos grafos, o Algoritmo de Edmonds-Karp é uma implementação do Algoritmo de Ford-Fulkerson para a resolução do em uma rede de fluxo. A característica que o distingue é que o caminho de aumento mais curto é usado em cada iteração, o que garante que o calculo vai terminar. Na maioria das implementações, o caminho de aumento mais curto é encontrado usando uma busca em largura, a qual roda em um tempo de . Isto é assintoticamente mais lento que , o qual roda em , mas é freqüentemente mais rápido para utilização em . O algoritmo foi publicado pela primeira vez pelo cientista russo , em 1970, e depois, de forma independente, por Edmonds e Karp que o publicaram em 1972. O algoritmo de Dinic inclui técnicas adicionais para reduzir o tempo para a ordem de .
|
| dbpedia-owl:thumbnail
| |
| dbpedia-owl:wikiPageExternalLink
| |
| dbpedia-owl:wikiPageID
| |
| dbpedia-owl:wikiPageRevisionID
| |
| comment
| - 计算机科学中，埃德蒙兹-卡普算法通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为。该算法由叶菲姆·迪尼茨在1970年最先提出，并由杰克·埃德蒙兹和在1972年独立发表。
- エドモンズ・カープのアルゴリズム（英: Edmonds-Karp algorithm）は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、 の計算量である。 のに比べると漸近的に遅いが、（辺の少ない）疎なグラフでは速い。このアルゴリズムは1970年にロシア人科学者 Dinic が発表し、それとは独立に1972年にとリチャード・カープが発表した（発見はこちらの方が早かった）。Dinic のアルゴリズムには追加の技法が含まれており、計算量は となっている。
- 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).
- Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время в графе . Впервые был опубликован в 1970 году советским учёным . Позже, в 1972 году, был независимо открыт Эдмондсом и Карпом.
- In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in time. The algorithm was first published by Yefim Dinitz (whose name is also transliterated "E. A. Dinic", notably as author of his early papers) in 1970 and independently published by Jack Edmonds and Richard Karp in 1972. Dinic's algorithm includes additional techniques that reduce the running time to . The Wikibook Algorithm implementation has a page on the topic of: Edmonds-Karp
- Edmondsův-Karpův algoritmus je v informatice a teorii grafů implementací Fordovy-Fulkersonovy metody pro výpočet maximálního toku v síti s časovou složitostí . Je asymptoticky pomalejší než Goldbergův algoritmus s časovou složitostí , ale v praxi je rychlejší pro . Dinic, ruský vědec, publikoval algoritmus poprvé v roce 1970 nezávisle na publikování stejného algoritmu Kanaďanem a Američanem Richardem Karpem v roce 1972 (údajně objeven dříve). Dinicův algoritmus obsahuje navíc techniky, které redukují časovou složitost na .
- Algorytm Edmondsa-Karpa jest jedną z realizacji metody Forda-Fulkersona rozwiązywania problemu maksymalnego przepływu w sieci przepływowej. Jego złożoność czasowa wynosi jest zatem wolniejszy od innych znanych algorytmów przepływowych działających w czasie takich jak algorytm relabel-to-front, czy . W praktyce jednak złożoność pesymistyczna rzadko jest osiągana, co w połączeniu z prostotą czyni algorytm Edmondsa-Karpa bardzo użytecznym, szczególnie dla grafów rzadkich.
- En informàtica i teoria de grafs, l'algorisme d'Edmonds–Karp és una especificació del de per calcular el flux màxim en una xarxa de flux amb cost . Aquest és assimpdòticament més lent que que té un cost de , però pot ser més ràpid en grafs dispersos. L'algorisme va ser publicat primer per un científic rus, Yefim (Chaim) Dinic, l'any 1970, i independentment per Jack Edmonds i Richard Karp el 1972 (però descobert abans). L'algorisme de Dinic inclou tècniques addicionals per reduir el temps d'execució a .
- En ciencias de la computación y teoría de grafos, el Algoritmo de Edmonds-Karp es una implementación del método de Ford-Fulkerson para calcular el flujo maximal en una red de flujo(i.e. computer network) con complejidad O(V E2). Es asintóticamente más lento que el , que tiene complejidad O(V3), pero es habitualmente más rápido en la práctica para grafos ralos. El algoritmo fue publicado por primera vez por un científico soviético, Yefim (Chaim) Dinic, en 1970, e independientemente por Jack Edmonds y Richard Karp en 1972. El Algoritmo de Dinic incluye técnicas adicionales para reducir la complejidad a O(V2E).
- Алгоритм Едмондса — Карпа розв'язує задачу знаходження максимального потоку в транспортній мережі. Алгоритм являє собою окремий випадок методу Форда-Фалкерсона і працює за час . Вперше був опублікований в 1970 році радянським вченим Ю. А. Деніцом. Пізніше, в 1972 році, був незалежно відкритий Едмондсом і Карпом. Алгоритм Дініца подає додаткові підходи для зменшення часу до .
- Der Edmonds-Karp-Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung des Ford-Fulkerson-Algorithmus zur Berechnung des maximalen s-t-Flusses in Netzwerken mit positiven reellen Kapazitäten. Sie verwendet den jeweils kürzesten augmentierenden Pfad in jedem Schritt, was sicherstellt, dass der Algorithmus in polynomieller Zeit terminiert.
- Na Ciência da computação e teoria dos grafos, o Algoritmo de Edmonds-Karp é uma implementação do Algoritmo de Ford-Fulkerson para a resolução do em uma rede de fluxo. A característica que o distingue é que o caminho de aumento mais curto é usado em cada iteração, o que garante que o calculo vai terminar. Na maioria das implementações, o caminho de aumento mais curto é encontrado usando uma busca em largura, a qual roda em um tempo de . Isto é assintoticamente mais lento que , o qual roda em , mas é freqüentemente mais rápido para utilização em . O algoritmo foi publicado pela primeira vez pelo cientista russo , em 1970, e depois, de forma independente, por Edmonds e Karp que o publicaram em 1972. O algoritmo de Dinic inclui técnicas adicionais para reduzir o tempo para a ordem de .
|
| label
| - Algorisme Edmonds-Karp
- Algorithme d'Edmonds-Karp
- Algorithmus von Edmonds und Karp
- Algoritmo de Edmonds-Karp
- Algoritmo de Edmonds-Karp
- Algorytm Edmondsa-Karpa
- Edmondsův–Karpův algoritmus
- Edmonds–Karp algorithm
- Алгоритм Едмондса — Карпа
- Алгоритм Эдмондса — Карпа
- エドモンズ・カープのアルゴリズム
- 埃德蒙兹-卡普算法
|
| dbpprop:wikiPageUsesTemplate
| |
| described by
| |
| topic
| |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
