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

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

Namespace Prefixes

Prefix	IRI
dbpedia-de	http://de.dbpedia.org/resource/
dcterms	http://purl.org/dc/terms/
dbo	http://dbpedia.org/ontology/
n24	http://dbpedia.org/resource/File:
foaf	http://xmlns.com/foaf/0.1/
dbpedia-ca	http://ca.dbpedia.org/resource/
dbpedia-es	http://es.dbpedia.org/resource/
n29	https://global.dbpedia.org/id/
yago	http://dbpedia.org/class/yago/
dbpedia-ru	http://ru.dbpedia.org/resource/
dbt	http://dbpedia.org/resource/Template:
dbpedia-uk	http://uk.dbpedia.org/resource/
rdfs	http://www.w3.org/2000/01/rdf-schema#
dbpedia-sr	http://sr.dbpedia.org/resource/
freebase	http://rdf.freebase.com/ns/
dbpedia-pt	http://pt.dbpedia.org/resource/
dbpedia-pl	http://pl.dbpedia.org/resource/
dbpedia-cs	http://cs.dbpedia.org/resource/
n14	http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fa	http://fa.dbpedia.org/resource/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
dbpedia-vi	http://vi.dbpedia.org/resource/
dbpedia-zh	http://zh.dbpedia.org/resource/
wikipedia-en	http://en.wikipedia.org/wiki/
dbpedia-fr	http://fr.dbpedia.org/resource/
dbp	http://dbpedia.org/property/
dbc	http://dbpedia.org/resource/Category:
prov	http://www.w3.org/ns/prov#
dbpedia-th	http://th.dbpedia.org/resource/
xsdh	http://www.w3.org/2001/XMLSchema#
gold	http://purl.org/linguistics/gold/
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/
dbpedia-ja	http://ja.dbpedia.org/resource/
dbpedia-ro	http://ro.dbpedia.org/resource/
n32	https://web.archive.org/web/20061005083406/http:/www.cis.upenn.edu/~wilf/

Statements

Subject Item

dbr:Push–relabel_maximum_flow_algorithm

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:List_of_algorithms

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Richard_M._Karp

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

dbp:knownFor

dbr:Edmonds–Karp_algorithm

dbo:knownFor

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Max-flow_min-cut_theorem

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Maximum_flow_problem

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Network_flow_problem

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Quadratic_pseudo-Boolean_optimization

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Timeline_of_algorithms

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Hopcroft–Karp_algorithm

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Widest_path_problem

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Cut_(graph_theory)

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Edmonds-Karp_algorithm

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

dbo:wikiPageRedirects

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Flow_network

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Dinic's_algorithm

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Edmonds–Karp_algorithm

rdf:type

yago:WikicatAlgorithms yago:Network108434259 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:WikicatNetworks yago:Activity100407535 dbo:Software yago:Act100030358 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:System108435388 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Abstraction100002137 yago:Group100031264

rdfs:label

Algorithme d'Edmonds-Karp Algorisme Edmonds-Karp Algorithmus von Edmonds und Karp 埃德蒙兹-卡普算法 Edmondsův–Karpův algoritmus Алгоритм Эдмондса — Карпа Algorytm Edmondsa-Karpa Edmonds–Karp algorithm Algoritmo de Edmonds-Karp エドモンズ・カープのアルゴリズム Algoritmo de Edmonds-Karp Алгоритм Едмондса — Карпа

rdfs:comment

Алгоритм Едмондса — Карпа розв'язує задачу знаходження максимального потоку в транспортній мережі. Алгоритм являє собою окремий випадок методу Форда-Фалкерсона і працює за час . Вперше був опублікований в 1970 році радянським вченим Ю. А. Деніцом. Пізніше, в 1972 році, був незалежно відкритий Едмондсом і Карпом. Алгоритм Дініца подає додаткові підходи для зменшення часу до . 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 . Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время в графе . Впервые был опубликован в 1970 году советским учёным . Позже, в 1972 году, был независимо открыт Эдмондсом и Карпом. 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 . エドモンズ・カープのアルゴリズム（英: Edmonds-Karp algorithm）は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、 の計算量である。 のに比べると漸近的に遅いが、（辺の少ない）疎なグラフでは速い。このアルゴリズムは1970年にロシア人科学者 Dinic が発表し、それとは独立に1972年にとリチャード・カープが発表した（発見はこちらの方が早かった）。Dinic のアルゴリズムには追加の技法が含まれており、計算量は となっている。 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. 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 . 计算机科学中，埃德蒙兹-卡普算法通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为。该算法由叶菲姆·迪尼茨在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 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). 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. 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).

foaf:depiction

n14:Edmonds-Karp_flow_example_0.svg n14:Edmonds-Karp_flow_example_1.svg n14:Edmonds-Karp_flow_example_2.svg n14:Edmonds-Karp_flow_example_3.svg n14:Edmonds-Karp_flow_example_4.svg

dcterms:subject

dbc:Graph_algorithms dbc:Network_flow_problem

dbo:wikiPageID

239230

dbo:wikiPageRevisionID

1082758324

dbo:wikiPageWikiLink

dbr:Computer_science dbr:Augmenting_path dbr:Jack_Edmonds dbr:Max_flow_min_cut_theorem dbr:Maximum_flow_problem dbr:Introduction_to_Algorithms dbc:Graph_algorithms dbr:Dinic's_algorithm n24:Edmonds-Karp_flow_example_0.svg n24:Edmonds-Karp_flow_example_1.svg dbc:Network_flow_problem n24:Edmonds-Karp_flow_example_2.svg n24:Edmonds-Karp_flow_example_3.svg n24:Edmonds-Karp_flow_example_4.svg dbr:Ford–Fulkerson_algorithm dbr:Breadth-first_search dbr:Flow_network dbr:Big_O_notation dbr:Richard_Karp

dbo:wikiPageExternalLink

n32:AlgComp3.html

owl:sameAs

dbpedia-pl:Algorytm_Edmondsa-Karpa dbpedia-es:Algoritmo_de_Edmonds-Karp freebase:m.01jprl dbpedia-vi:Thuật_toán_Edmonds–Karp dbpedia-fr:Algorithme_d'Edmonds-Karp dbpedia-ca:Algorisme_Edmonds-Karp dbpedia-ro:Algoritmul_Edmonds-Karp dbpedia-zh:埃德蒙兹-卡普算法 dbpedia-ja:エドモンズ・カープのアルゴリズム dbpedia-uk:Алгоритм_Едмондса_—_Карпа dbpedia-cs:Edmondsův–Karpův_algoritmus dbpedia-de:Algorithmus_von_Edmonds_und_Karp n29:Kspz dbpedia-fa:الگوریتم_ادموندز_کارپ wikidata:Q1302658 dbpedia-ru:Алгоритм_Эдмондса_—_Карпа dbpedia-pt:Algoritmo_de_Edmonds-Karp dbpedia-th:ขั้นตอนวิธีของเอ็ดมอนด์-คาป dbpedia-sr:Едмондс–Карпов_алгоритам

dbp:wikiPageUsesTemplate

dbt:Optimization_algorithms dbt:Wikibooks dbt:Use_American_English dbt:Reflist dbt:Short_description

dbo:thumbnail

n14:Edmonds-Karp_flow_example_0.svg?width=300

dbo:abstract

Алгоритм Едмондса — Карпа розв'язує задачу знаходження максимального потоку в транспортній мережі. Алгоритм являє собою окремий випадок методу Форда-Фалкерсона і працює за час . Вперше був опублікований в 1970 році радянським вченим Ю. А. Деніцом. Пізніше, в 1972 році, був незалежно відкритий Едмондсом і Карпом. Алгоритм Дініца подає додаткові підходи для зменшення часу до . 计算机科学中，埃德蒙兹-卡普算法通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为。该算法由叶菲姆·迪尼茨在1970年最先提出，并由杰克·埃德蒙兹和在1972年独立发表。 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). 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 . エドモンズ・カープのアルゴリズム（英: Edmonds-Karp algorithm）は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、 の計算量である。 のに比べると漸近的に遅いが、（辺の少ない）疎なグラフでは速い。このアルゴリズムは1970年にロシア人科学者 Dinic が発表し、それとは独立に1972年にとリチャード・カープが発表した（発見はこちらの方が早かった）。Dinic のアルゴリズムには追加の技法が含まれており、計算量は となっている。 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). 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 . 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 Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время в графе . Впервые был опубликован в 1970 году советским учёным . Позже, в 1972 году, был независимо открыт Эдмондсом и Карпом. 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 . 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). 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 .

gold:hypernym

dbr:Implementation

prov:wasDerivedFrom

wikipedia-en:Edmonds–Karp_algorithm?oldid=1082758324&ns=0

dbo:wikiPageLength

7532

foaf:isPrimaryTopicOf

wikipedia-en:Edmonds–Karp_algorithm

Subject Item

dbr:Ford–Fulkerson_algorithm

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:GrabCut

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Graph_cut_optimization

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Graph_theory

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Jack_Edmonds

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

dbo:knownFor

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Circulation_problem

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Edmonds-Karp

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

dbo:wikiPageRedirects

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Edmonds_Karp

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

dbo:wikiPageRedirects

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Edmonds_karp

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

dbo:wikiPageRedirects

dbr:Edmonds–Karp_algorithm

Subject Item

dbr:Edmonds–Karp

dbo:wikiPageWikiLink

dbr:Edmonds–Karp_algorithm

dbo:wikiPageRedirects

dbr:Edmonds–Karp_algorithm

Subject Item

wikipedia-en:Edmonds–Karp_algorithm

foaf:primaryTopic

dbr:Edmonds–Karp_algorithm