unserLexikon

Algorithmus von Edmonds und Karp


(Weitergeleitet von Edmonds-Karp-Algorithmus)

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.[1]

In den meisten Implementierungen wird der kürzeste Pfad durch eine Breitensuche ermittelt, was zu einer Laufzeit in \({\displaystyle {\mathcal {O}}(|V|\cdot |E|^{2})}\) führt.[2] 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 \({\displaystyle {\mathcal {O}}(|V|^{2}\cdot |E|)}\).


Literatur

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7, Unterkapitel 26.2: The Ford-Fulkerson method, S. 651–664.
  • Bernhard Korte, Jens Vygen: Kombinatorische Optimierung. Springer Berlin Heidelberg, 2012, ISBN 978-3-642-25400-0, Unterkapitel 8.3: Der Edmonds-Karp-Algorithmus, S. 195–196.

Einzelnachweise

  1. Jack Edmonds, Richard M. Karp: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. In: J. ACM. Band 19, Nr. 2, 1972, S. 248–264, doi:10.1145/321694.321699
  2. Santanu Saha Ray: Graph Theory with Algorithms and its Applications. 1. Auflage. Springer India, New Delhi, u. a. 2013, ISBN 978-81-322-0749-8, S. 167–175. 




Quelle


Stand der Informationen: 16.12.2021 06:21:33 UTC

Quelle: Wikipedia (Autoren [Versionsgeschichte])    Lizenz des Textes: CC-BY-SA-3.0. Urheber und Lizenzen der einzelnen Bilder und Medien sind entweder in der Bildunterschrift zu finden oder können durch Anklicken des Bildes angezeigt werden.

Veränderungen: Designelemente wurden umgeschrieben. Wikipedia spezifische Links (wie bspw "Redlink", "Bearbeiten-Links"), Karten, Niavgationsboxen wurden entfernt. Ebenso einige Vorlagen. Icons wurden durch andere Icons ersetzt oder entfernt. Externe Links haben ein zusätzliches Icon erhalten.

Wichtiger Hinweis Unsere Inhalte wurden zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen. Eine manuelle Überprüfung war und ist daher nicht möglich. Somit garantiert unserLexikon.de nicht die Aktualität und Richtigkeit der übernommenen Inhalte. Falls die Informationen mittlerweile fehlerhaft sind oder Fehler vorliegen, bitten wir Sie uns zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.