Graph cut optimization: Difference between revisions

Revision as of 00:26, 4 May 2024

Revision as of 23:25, 20 July 2024

Line 89:

== Minimum cut ==

After building a graph representing a pseudo-Boolean function, it is possible to compute a minimum cut using one among the various algorithms developed for flow networks, such as [[Ford–Fulkerson algorithm|Ford–Fulkerson]], [[Edmonds–Karp algorithm|Edmonds–Karp]], and [[Boykov–Kolmogorov algorithm]]. The result is a partition of the graph in two connected components <math>S</math> and <math>T</math> such that <math>s \in S</math> and <math>t \in T</math>, and the function attains its global minimum when <math>x_i = 0</math> for each <math>i</math> such that the corresponding node <math>v_i \in

S</math>, and <math>x_i = 1</math> for each <math>i</math> such that the corresponding node <math>v_i \in T</math>.

Max-flow algorithms such as Boykov&ndash;Kolmogorov's are very efficient in practice for sequential computation, but they are difficult to parallelise, making them not suitable for [[distributed computing]] applications and preventing them from exploiting the potential of modern [[Central Processing Unit|CPU]]s. Parallel max-flow algorithms were developed, such as [[Push–relabel maximum flow algorithm|push-relabel]]<ref name="goldberg" /> and [[jump-flood algorithm|jump-flood]],<ref name="peng" /> that can also take advantage of hardware acceleration in [[GPGPU]] implementations.<ref name="cudacuts" /><ref name="peng" /><ref name="stich" />

== Functions of discrete variables with more than two values ==