Dinic's algorithm
http://dbpedia.org/resource/Dinic's_algorithm an entity of type: Abstraction100002137
Dinicův algoritmus je algoritmus vyvinutý Jefimem Dinicem (1970) pro výpočet maximálního toku v síti. Hlavní myšlenka algoritmu spočívá v iterativním výpočtu tzv. "blokujících" toků, které se postupně nasčítají až na tok maximální. Tento přístup dovoluje v průměrném případě počítat maximální tok rychleji než Fordovým–Fulkersonovým algoritmem, který pro výpočet využívá hledání zlepšujících cest.
rdf:langString
Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in time and is similar to the Edmonds–Karp algorithm, which runs in time, in that it uses shortest augmenting paths. The introduction of the concepts of the level graph and blocking flow enable Dinic's algorithm to achieve its performance.
rdf:langString
Der Algorithmus von Dinic ist ein Algorithmus aus der Graphentheorie zur Bestimmung eines maximalen Flusses in einem Netzwerk. Er wurde von (Jefim (Chaim) Dinic) entwickelt und 1970 publiziert. Er ist eine Weiterentwicklung des Edmonds-Karp-Algorithmus, den Dinic unabhängig von Jack Edmonds und Richard M. Karp entwickelte. Der Algorithmus von Dinic unterscheidet sich vom Edmonds-Karp-Algorithmus, indem in jedem Durchgang nicht nur an einem einzelnen kürzesten s-t-Weg augmentiert wird, sondern mitunter an größeren s-t-Flüssen, die sich aus mehreren kürzesten s-t-Wegen zusammensetzen.
rdf:langString
El algoritmo de Dinic es un algoritmo de Tiempo polinómico para la computación de un Flujo maximal en una red de flujo, concebida en 1970 por el científico de la computación , israelí de origen soviético. El algoritmo es ejecutado en un tiempo de y está basado en el Algoritmo de Edmonds-Karp, el cual a su vez se ejecuta en un tiempo , y utiliza trayectorias de aumento más cortas. La introducción de los conceptos nivel de grafo y bloqueo de flujo es lo que define el rendimiento del algoritmo de Dinic.
rdf:langString
L'algorithme de Dinic ou algorithme de Dinitz est un algorithme en temps polynomial (et même fortement polynomial) de calcul du flot maximum dans un réseau, publié en 1970 par Yefim Dinitz.Le temps de calcul est en pour un graphe dont est l'ensemble des sommets et l’ensemble des arcs. Il est semblable à l'algorithme d'Edmonds-Karp dont le temps d'exécution est en . Comme lui, il utilise des chemins augmentants de longueur minimale. L'introduction des concepts de graphe de niveau et de flot bloquant permet d'obtenir cette meilleure performance.
rdf:langString
Algorytm Dynica – algorytm o złożoności czasowej rozwiązujący problem maksymalnego przepływu w sieci przepływowej umożliwiający odnajdywanie przepływu blokującego w . Algorytm skonstruowany został w 1970 roku przez izraelskiego profesora - . Strukturą zbliżony jest do alg. Edmondsa-Karpa. 1.
* krok - dziel graf na L warstw (przegląd wszerz) 2.
* krok - utwórz ścieżki powiększające (przegląd w głąb), nie przemieszczając się względem tej samej warstwy 3.
* krok - wyznacz maksymalny przepływ
rdf:langString
Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком . Временная сложность алгоритма составляет . Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности: .
rdf:langString
Алгоритм Дініца — поліноміальний алгоритм для знаходження максимального потоку у транспортної мережі, запропонований 1970 року ізраїльським (колишнім радянським) ученим Юхимом Дініцем. І алгоритм Дініца, і алгоритм Едмондса–Карпа незалежно показують, що в алгоритмі Форда — Фалкерсона в разі найкоротшого доповнювального шляху його довжина доповнює шляху не зменшується. Часова складність алгоритму становить . Отримати таку оцінку дозволяє введення понять допоміжної мережі та блокуючого (псевдомаксимального) потоку. В мережах з одиничними пропускними здатностями існує сильніша оцінка часової складності: .
rdf:langString
迪尼茨算法是在网络流计算最大流的强多项式复杂度的算法，设想由以色列计算机科学家叶菲姆·迪尼茨在1970年提出。算法的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号（level graph）以及阻塞流（blocking flow）实现性能。
rdf:langString
rdf:langString
Dinicův algoritmus
rdf:langString
Algorithmus von Dinic
rdf:langString
Algoritmo de Dinic
rdf:langString
Dinic's algorithm
rdf:langString
Algorithme de Dinic
rdf:langString
Algorytm Dynica
rdf:langString
Алгоритм Диница
rdf:langString
Алгоритм Дініца
rdf:langString
迪尼茨算法
xsd:integer
23635821
xsd:integer
1119884267
rdf:langString
Dinicův algoritmus je algoritmus vyvinutý Jefimem Dinicem (1970) pro výpočet maximálního toku v síti. Hlavní myšlenka algoritmu spočívá v iterativním výpočtu tzv. "blokujících" toků, které se postupně nasčítají až na tok maximální. Tento přístup dovoluje v průměrném případě počítat maximální tok rychleji než Fordovým–Fulkersonovým algoritmem, který pro výpočet využívá hledání zlepšujících cest.
rdf:langString
Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in time and is similar to the Edmonds–Karp algorithm, which runs in time, in that it uses shortest augmenting paths. The introduction of the concepts of the level graph and blocking flow enable Dinic's algorithm to achieve its performance.
rdf:langString
Der Algorithmus von Dinic ist ein Algorithmus aus der Graphentheorie zur Bestimmung eines maximalen Flusses in einem Netzwerk. Er wurde von (Jefim (Chaim) Dinic) entwickelt und 1970 publiziert. Er ist eine Weiterentwicklung des Edmonds-Karp-Algorithmus, den Dinic unabhängig von Jack Edmonds und Richard M. Karp entwickelte. Der Algorithmus von Dinic unterscheidet sich vom Edmonds-Karp-Algorithmus, indem in jedem Durchgang nicht nur an einem einzelnen kürzesten s-t-Weg augmentiert wird, sondern mitunter an größeren s-t-Flüssen, die sich aus mehreren kürzesten s-t-Wegen zusammensetzen.
rdf:langString
El algoritmo de Dinic es un algoritmo de Tiempo polinómico para la computación de un Flujo maximal en una red de flujo, concebida en 1970 por el científico de la computación , israelí de origen soviético. El algoritmo es ejecutado en un tiempo de y está basado en el Algoritmo de Edmonds-Karp, el cual a su vez se ejecuta en un tiempo , y utiliza trayectorias de aumento más cortas. La introducción de los conceptos nivel de grafo y bloqueo de flujo es lo que define el rendimiento del algoritmo de Dinic.
rdf:langString
L'algorithme de Dinic ou algorithme de Dinitz est un algorithme en temps polynomial (et même fortement polynomial) de calcul du flot maximum dans un réseau, publié en 1970 par Yefim Dinitz.Le temps de calcul est en pour un graphe dont est l'ensemble des sommets et l’ensemble des arcs. Il est semblable à l'algorithme d'Edmonds-Karp dont le temps d'exécution est en . Comme lui, il utilise des chemins augmentants de longueur minimale. L'introduction des concepts de graphe de niveau et de flot bloquant permet d'obtenir cette meilleure performance.
rdf:langString
Algorytm Dynica – algorytm o złożoności czasowej rozwiązujący problem maksymalnego przepływu w sieci przepływowej umożliwiający odnajdywanie przepływu blokującego w . Algorytm skonstruowany został w 1970 roku przez izraelskiego profesora - . Strukturą zbliżony jest do alg. Edmondsa-Karpa. 1.
* krok - dziel graf na L warstw (przegląd wszerz) 2.
* krok - utwórz ścieżki powiększające (przegląd w głąb), nie przemieszczając się względem tej samej warstwy 3.
* krok - wyznacz maksymalny przepływ
rdf:langString
Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком . Временная сложность алгоритма составляет . Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности: .
rdf:langString
Алгоритм Дініца — поліноміальний алгоритм для знаходження максимального потоку у транспортної мережі, запропонований 1970 року ізраїльським (колишнім радянським) ученим Юхимом Дініцем. І алгоритм Дініца, і алгоритм Едмондса–Карпа незалежно показують, що в алгоритмі Форда — Фалкерсона в разі найкоротшого доповнювального шляху його довжина доповнює шляху не зменшується. Часова складність алгоритму становить . Отримати таку оцінку дозволяє введення понять допоміжної мережі та блокуючого (псевдомаксимального) потоку. В мережах з одиничними пропускними здатностями існує сильніша оцінка часової складності: .
rdf:langString
迪尼茨算法是在网络流计算最大流的强多项式复杂度的算法，设想由以色列计算机科学家叶菲姆·迪尼茨在1970年提出。算法的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号（level graph）以及阻塞流（blocking flow）实现性能。
xsd:nonNegativeInteger
10875
