Max-flow min-cut theorem
id:
max-flow-min-cut-theorem-187-15123000
title:
Max-flow min-cut theorem
text:
In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink. This is a special case of the duality theorem for linear programs and can be used to derive Menger's theorem and the Kőnig–Egerváry theorem.
brand slug:
wiki
category slug:
encyclopedia
description:
Concept in optimization theory
original url:
https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
date created:
2002-08-30T20:17:42Z
date modified:
2024-09-08T15:14:31Z
main entity:
{"identifier":"Q608294","url":"https://www.wikidata.org/entity/Q608294"}
image:
fields total:
13
integrity:
15