Algorithmus von Edmonds und Karp

Der Edmonds-Karp-Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung der Ford-Fulkerson-Methode 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 \mathcal{O}(|V| \cdot |E|^2) führt. Der Algorithmus wurde zuerst 1970 von dem russischen Wissenschaftler E. A. Dinic 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 \mathcal{O}(|V|^2 \cdot |E|).

Quellen

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 26.2: The Ford-Fulkerson method, pp.651–664.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Ford und Fulkerson — Der Algorithmus von Ford und Fulkerson (nach seinen Erfindern Lester Randolph Ford junior und Delbert Ray Fulkerson[1]) dient der Berechnung eines maximalen s t Flusses in einem Netzwerk. Er sucht sukzessiv nach flussvergrößernden Pfaden im… …   Deutsch Wikipedia

  • Algorithmus von Dinic — Der Algorithmus von Dinic ist ein Algorithmus aus der Graphentheorie zur Bestimmung eines maximalen s t Flusses in einem Netzwerk. Er wurde von E. A. Dinic (Jefim (Chaim) Dinic) entwickelt und 1970 publiziert. Er ist eine Weiterentwicklung des… …   Deutsch Wikipedia

  • Edmonds — ist der Familienname folgender Personen: Barry Edmonds (1931–1982), US amerikanischer Fotojournalist Beth Edmonds, US Senatorin und Frauenrechtlerin Don Edmonds (1937–2009), US amerikanischer Filmregisseur und produzent Duncan Edmonds (* 1936),… …   Deutsch Wikipedia

  • Edmonds-Karp-Algorithmus — Der Edmonds Karp Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung der Ford Fulkerson Methode zur Berechnung des maximalen Flusses in Netzwerken. Sie verwendet den jeweils kürzesten augmentierenden Pfad in jedem… …   Deutsch Wikipedia

  • Flüsse und Schnitte in Netzwerken — sind Strukturen der Graphentheorie, die vielfältige Anwendungen finden. Inhaltsverzeichnis 1 Definitionen, wichtige Begriffe und Eigenschaften 1.1 Netzwerk 1.2 Fluss 1.2.1 …   Deutsch Wikipedia

  • Ford-Fulkerson-Algorithmus — Der Algorithmus von Ford und Fulkerson (nach seinen Erfindern Lester Randolph Ford junior und Delbert Ray Fulkerson[1]) dient der Berechnung eines maximalen Flusses in einem Netzwerk. Er sucht sukzessive nach flussvergrößernden Pfaden, vergrößert …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Richard M. Karp — Richard Karp 2009 Richard Manning Karp (* 3. Januar 1935 in Boston, Massachusetts) ist ein amerikanischer Informatiker. Er ist verantwortlich für bedeutende Erkenntnisse in der Komplexitätstheorie. 1985 erhielt er für seine Forschungsarbeit auf… …   Deutsch Wikipedia

  • Matching (Graphentheorie) — Die Theorie um das Finden von Matchings in Graphen ist in der diskreten Mathematik ein umfangreiches Teilgebiet, das in die Graphentheorie eingeordnet wird. Folgende Situation wird dabei betrachtet: Gegeben eine Menge von Dingen und zu diesen… …   Deutsch Wikipedia

  • Fluss (Graphentheorie) — Ein Netzwerk N=(V, E, s, t, c) ist in der Graphentheorie ein gerichteter Graph ohne Mehrfachkanten mit zwei ausgezeichneten Knoten, einer Quelle s und einer Senke t aus V sowie einer Kapazitätsfunktion c, die jeder Kante (x,y) aus E eine nicht… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”