A simple version of Karzanov's blocking flow algorithm (Q795064): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(4 intermediate revisions by 3 users not shown)
Property / reviewed by
 
Property / reviewed by: Louis Caccetta / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Louis Caccetta / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0167-6377(84)90076-2 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1991295190 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5624995 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3883524 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: An \(O(EV\log^2V)\) algorithm for the maximal flow problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4058442 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4057549 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4130999 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An \(O(IVI^3)\) algorithm for finding maximum flows in networks / rank
 
Normal rank
Property / cites work
 
Property / cites work: An O(n2log n) parallel max-flow algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding Dominators in Directed Graphs / rank
 
Normal rank

Latest revision as of 12:10, 14 June 2024

scientific article
Language Label Description Also known as
English
A simple version of Karzanov's blocking flow algorithm
scientific article

    Statements

    A simple version of Karzanov's blocking flow algorithm (English)
    0 references
    1984
    0 references
    A network is a directed graph G with two distinguished vertices, a source s and a sink t, and a positive capacity c(v,w) on every edge [v,w]. A flow is blocking if there is a saturated edge on every path from s to t. \textit{E. A. Dinits} [Sov. Math., Dokl. 11, 1277-1280 (1970); translation from Dokl. Akad. Nauk SSSR 194, 754-757 (1970; Zbl 0219.90046)] has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of, at most n-1 so- called ''blocking flow'' problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problem is \(O(n^ 2)\) [\textit{A. V. Karzanov}, Sov. Math. Dokl. 15(1974), 434-437 (1975; Zbl 0303.90014); \textit{V. M. Malhotra, M. P. Kumar} and \textit{S. N. Maheshwari}, Inf. Process. Lett. 7, 277-278 (1978; Zbl 0391.90041)]. In this paper the author presents a version of Karzanov's algorithm that is easy to implement.
    0 references
    graph algorithm
    0 references
    maximum flow problem
    0 references

    Identifiers