| dbo:abstract
|
- Goldbergův algoritmus hledá maximální tok v síti v čase . Patří do třídy algoritmů s operacemi přemístění přebytku a zvedání vrcholu na nalezení maximálního toku, které mají . Pro husté grafy je efektivnější než Edmonds-Karpův algoritmus, který má časovou složitost . V anglické literatuře se Goldbergův algoritmus též nazývá algoritmem preflow-push nebo relabel-to-front. (cs)
- Der Goldberg-Tarjan-Algorithmus, auch Push-Relabel-Algorithmus genannt, ist ein Algorithmus aus der Graphentheorie zur Berechnung eines maximalen Flusses in einem Netzwerk. Er wurde von Andrew Goldberg und Robert Endre Tarjan entwickelt und 1988 publiziert. (de)
- L'algorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986. L'algorithme général a une complexité en temps en (ici est l'ensemble des sommets, et l'ensemble des arcs du graphe) ; une implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en ; une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité . Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un (en) donne un temps d'exécution majoré par . Tous ces temps sont meilleurs que la majoration en qui est celle de l'algorithme d'Edmonds-Karp. (fr)
- In mathematical optimization, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink. The push–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a strongly polynomial O(V 2E) time complexity, which is asymptotically more efficient than the O(VE 2) Edmonds–Karp algorithm. Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label node selection rule has O(V 2√E) time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic O(VElog(V 2/E)) time complexity can be achieved using dynamic trees, although in practice it is less efficient. The push–relabel algorithm has been extended to compute minimum cost flows. The idea of distance labels has led to a more efficient augmenting path algorithm, which in turn can be incorporated back into the push–relabel algorithm to create a variant with even higher empirical performance. (en)
- Algorytm push-relabel – jeden z najbardziej efektywnych algorytmów obliczania maksymalnego przepływu. Ogólny algorytm działa ze złożonością podczas gdy modyfikacja Relabel-to-Front ma złożoność czasową rozwiązanie z wyborem najbardziej aktywnego wierzchołka a implementacja z dynamicznym drzewem Sleatora-Tarajana Asymptotycznie, algorytm ten jest znacznie bardziej efektywny niż algorytm Edmondsa-Karpa, którego złożoność czasowa wynosi (pl)
- Алгоритм проталкивания предпотока решает задачу нахождения максимального потока в транспортной сети. Алгоритм не является частным случаем алгоритма Форда-Фалкерсона. Реализованный без специальных усовершенствований, алгоритм выполняется за время . Некоторые усовершенствования ещё ускоряют алгоритм: правило выбора вершин «поднять в начало» - до , выбор высшей активной вершины - до , реализация с использованием структуры данных Сеанора (Seanor) и Тарьяна - до . Впервые был опубликован в 1986 году Гольдбергом (Andrew W. Goldberg) и Тарьяном.. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 35860 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:align
| |
| dbp:alt
|
- Final maximum flow network graph (en)
- Initial flow network graph (en)
|
| dbp:border
| |
| dbp:caption
|
- Final maximum flow network graph (en)
- Initial flow network graph (en)
|
| dbp:image
|
- Push Relabel Algoritm Example - Initial Graph.svg (en)
- Push-Relabel Algorithm Example - Final Network Graph.svg (en)
|
| dbp:title
|
- Python implementation (en)
- C implementation (en)
|
| dbp:titlestyle
| |
| dbp:width
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Goldbergův algoritmus hledá maximální tok v síti v čase . Patří do třídy algoritmů s operacemi přemístění přebytku a zvedání vrcholu na nalezení maximálního toku, které mají . Pro husté grafy je efektivnější než Edmonds-Karpův algoritmus, který má časovou složitost . V anglické literatuře se Goldbergův algoritmus též nazývá algoritmem preflow-push nebo relabel-to-front. (cs)
- Der Goldberg-Tarjan-Algorithmus, auch Push-Relabel-Algorithmus genannt, ist ein Algorithmus aus der Graphentheorie zur Berechnung eines maximalen Flusses in einem Netzwerk. Er wurde von Andrew Goldberg und Robert Endre Tarjan entwickelt und 1988 publiziert. (de)
- Algorytm push-relabel – jeden z najbardziej efektywnych algorytmów obliczania maksymalnego przepływu. Ogólny algorytm działa ze złożonością podczas gdy modyfikacja Relabel-to-Front ma złożoność czasową rozwiązanie z wyborem najbardziej aktywnego wierzchołka a implementacja z dynamicznym drzewem Sleatora-Tarajana Asymptotycznie, algorytm ten jest znacznie bardziej efektywny niż algorytm Edmondsa-Karpa, którego złożoność czasowa wynosi (pl)
- Алгоритм проталкивания предпотока решает задачу нахождения максимального потока в транспортной сети. Алгоритм не является частным случаем алгоритма Форда-Фалкерсона. Реализованный без специальных усовершенствований, алгоритм выполняется за время . Некоторые усовершенствования ещё ускоряют алгоритм: правило выбора вершин «поднять в начало» - до , выбор высшей активной вершины - до , реализация с использованием структуры данных Сеанора (Seanor) и Тарьяна - до . Впервые был опубликован в 1986 году Гольдбергом (Andrew W. Goldberg) и Тарьяном.. (ru)
- L'algorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986. L'algorithme général a une complexité en temps en (ici est l'ensemble des sommets, et l'ensemble des arcs du graphe) ; une implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en ; une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité . Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un (fr)
- In mathematical optimization, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink. (en)
|
| rdfs:label
|
- Goldbergův algoritmus (cs)
- Goldberg-Tarjan-Algorithmus (de)
- Algorithme de poussage/réétiquetage (fr)
- Push–relabel maximum flow algorithm (en)
- Algorytm push-relabel (pl)
- Алгоритм проталкивания предпотока (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
