Algorithmus von Edmonds und Karp


(Weitergeleitet von Edmonds-Karp-Algorithmus)

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


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.
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Algorithmus_von_Edmonds_und_Karp&oldid=220158776

Navigationsmenü


<



Facebook Twitter WhatsApp Telegram E-Mail





Kategorien: Netzwerktheorie | Algorithmus | Algorithmus (Graphentheorie) | Optimierungsalgorithmus




Stand der Informationen: 15.02.2022 01:23:57 CET

Quelle: Wikipedia (Autoren [Versionsgeschichte])    Lizenz: CC-BY-SA-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.

Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.