Dinic's algorithm
id:
dinic-s-algorithm-187-15040908
title:
Dinic's algorithm
text:
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 computer scientist Yefim Dinitz. The algorithm runs in O time and is similar to the Edmonds–Karp algorithm, which runs in O 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.
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Dinic%27s_algorithm
date created:
2009-07-17T04:59:50Z
date modified:
2024-09-08T15:10:15Z
main entity:
{"identifier":"Q730933","url":"https://www.wikidata.org/entity/Q730933"}
image:
fields total:
13
integrity:
14