Content deleted Content added
→Minimum cut: typo |
Newslinger (talk | contribs) Adding local short description: "Combinatorial optimization method for a family of functions of discrete variables" (Shortdesc helper) |
||
Line 1:
{{short description|Combinatorial optimization method for a family of functions of discrete variables}}
'''Graph cut optimization''' is a [[combinatorial optimization]] method applicable to a family of [[function (mathematics)|function]]s of [[Continuous or discrete variable|discrete variable]]s, named after the concept of [[cut (graph theory)|cut]] in the theory of [[flow network]]s. Thanks to the [[max-flow min-cut theorem]], determining the [[minimum cut]] over a [[graph (discrete mathematics)|graph]] representing a flow network is equivalent to computing the [[maximum flow]] over the network. Given a [[pseudo-Boolean function]], if it is possible to construct a flow network such that the variables of the function are represented by nodes in the network, and for each possible cut the value of the flow equals the value of the function when each variable assumes a binary value depending on the belonging of its representing node to the source or sink component after the cut, then it is possible to find the [[global optimum]] of such function in [[polynomial time]] by computing a minimum cut of the graph.
| |||