Optimización de corte de grafos

La optimización de cortes de grafos es un método de optimización combinatoria aplicable a una familia de funciones de variables discretas , que recibe su nombre del concepto de corte en la teoría de redes de flujo . Gracias al teorema de flujo máximo y corte mínimo , determinar el corte mínimo sobre un grafo que representa una red de flujo es equivalente a calcular el flujo máximo sobre la red. Dada una función pseudo-booleana${\displaystyle f}$, si es posible construir una red de flujo con pesos positivos tal que

• cada corte${\displaystyle C}$de la red se puede mapear a una asignación de variables${\displaystyle \mathbf {x} }$a${\displaystyle f}$(y viceversa), y
• el costo de${\displaystyle C}$igual${\displaystyle f(\mathbf {x} )}$(hasta una constante aditiva)

entonces es posible encontrar el óptimo global de${\displaystyle f}$en tiempo polinomial calculando un corte mínimo del grafo. La correspondencia entre los cortes y las asignaciones de variables se realiza representando cada variable con un nodo en el grafo y, dado un corte, cada variable tendrá un valor de 0 si el nodo correspondiente pertenece al componente conectado a la fuente, o de 1 si pertenece al componente conectado al sumidero.

No todas las funciones pseudobooleanas pueden representarse mediante una red de flujo, y en el caso general, el problema de optimización global es NP-difícil . Existen condiciones suficientes para caracterizar familias de funciones que pueden optimizarse mediante cortes de grafos, como las funciones cuadráticas submodulares . La optimización mediante cortes de grafos puede extenderse a funciones de variables discretas con un número finito de valores, que pueden abordarse con algoritmos iterativos con fuertes propiedades de optimalidad, calculando un corte de grafo en cada iteración.

La optimización de cortes de grafos es una herramienta importante para la inferencia sobre modelos gráficos como campos aleatorios de Markov o campos aleatorios condicionales , y tiene aplicaciones en problemas de visión por computadora como la segmentación de imágenes , ^{[ 1 ] [ 2 ]} la eliminación de ruido , ^{[ 3 ]} el registro ^{[ 4 ] [ 5 ]} y la correspondencia estéreo . ^{[ 6 ] [ 7 ]}

Una función pseudobooleana${\displaystyle f:\{0,1\}^{n}\to \mathbb {R} }$Se dice que es representable si existe un gráfico.${\displaystyle G=(V,E)}$con pesos no negativos y con nodos de origen y destino${\displaystyle s}$y${\displaystyle t}$respectivamente, y existe un conjunto de nodos${\displaystyle V_{0}=\{v_{1},\dots ,v_{n}\}\subset V-\{s,t\}}$de tal manera que, para cada tupla de valores${\displaystyle (x_{1},\dots ,x_{n})\in \{0,1\}^{n}}$asignado a las variables,${\displaystyle f(x_{1},\dots ,x_{n})}$es igual (salvo una constante) al valor del flujo determinado por un corte mínimo${\displaystyle C=(S,T)}$del gráfico${\displaystyle G}$de tal manera que${\displaystyle v_{i}\in S}$si${\displaystyle x_{i}=0}$y${\displaystyle v_{i}\in T}$si${\displaystyle x_{i}=1}$. ^{[ 8 ]}

Es posible clasificar las funciones pseudobooleanas según su orden, determinado por el número máximo de variables que contribuyen a cada término. Todas las funciones de primer orden, donde cada término depende como máximo de una variable, son siempre representables. Funciones cuadráticas

${\displaystyle f(\mathbf {x} )=w_{0}+\sum _{i}w_{i}(x_{i})+\sum _{i<j}w_{ij}(x_{i},x_{j}).}$

son representables si y solo si son submodulares, es decir, para cada término cuadrático${\displaystyle w_{ij}}$Se cumple la siguiente condición.

${\displaystyle w_{ij}(0,0)+w_{ij}(1,1)\leq w_{ij}(0,1)+w_{ij}(1,0).}$

Funciones cúbicas

${\displaystyle f(\mathbf {x} )=w_{0}+\sum _{i}w_{i}(x_{i})+\sum _{i<j}w_{ij}(x_{i},x_{j})+\sum _{i<j<k}w_{ijk}(x_{i},x_{j},x_{k})}$

Son representables si y solo si son regulares , es decir, todas las posibles proyecciones binarias a dos variables, obtenidas fijando el valor de la variable restante, son submodulares. Para funciones de orden superior, la regularidad es una condición necesaria para la representabilidad. ^{[ 8 ]}

La construcción gráfica de una función representable se simplifica por el hecho de que la suma de dos funciones representables${\displaystyle f'}$y${\displaystyle f''}$es representable y su gráfico${\displaystyle G=(V'\taza V'',E'\taza E'')}$es la unión de los gráficos${\displaystyle G'=(V',E')}$y${\displaystyle G''=(V'',E'')}$representando las dos funciones. Dicho teorema permite construir gráficas separadas que representan cada término y combinarlas para obtener una gráfica que representa la función completa . ^{[ 8 ]}

La gráfica que representa una función cuadrática de${\displaystyle n}$Las variables contienen${\displaystyle n+2}$vértices, dos de ellos representan la fuente y el sumidero, y los demás representan las variables. Al representar funciones de orden superior, el grafo contiene nodos auxiliares que permiten modelar interacciones de orden superior.

Términos binarios

Un término cuadrático (o binario)${\displaystyle w_{ij}}$puede representarse mediante un grafo que contiene dos nodos no terminales.${\displaystyle v_{i}}$y${\displaystyle v_{j}}$El término puede reescribirse como

${\displaystyle w_{ij}(x_{i},x_{j})=w_{ij}(0,0)+k_{i}x_{i}+k_{j}x_{j}+k_{ij}\left((1-x_{i})x_{j}+x_{i}(1-x_{j})\right)}$

con

${\displaystyle {\begin{aligned}k_{i}&={\frac {1}{2}}(w_{ij}(1,0)-w_{ij}(0,0))\\k_{j}&={\frac {1}{2}}(w_{ij}(1,1)-w_{ij}(1,0))\\k_{ij}&={\frac {1}{2}}(w_{ij}(0,1)+w_{ij}(1,0)-w_{ij}(0,0)-w_{ij}(1,1)).\end{aligned}}}$

En esta expresión, el primer término es constante y no está representado por ninguna arista, los dos términos siguientes dependen de una variable y están representados por una arista, como se muestra en la sección anterior para términos unarios, mientras que el tercer término está representado por una arista.${\displaystyle v_{i}\rightarrow v_{j}}$con peso${\displaystyle w_{ij}(0,1)+w_{ij}(1,0)-w_{ij}(0,0)-w_{ij}(1,1)}$(la submodularidad garantiza que el peso sea no negativo). ^{[ 8 ]}

Términos ternarios

Un término cúbico (o ternario)${\displaystyle w_{ijk}}$puede representarse mediante un grafo con cuatro nodos no terminales, tres de ellos (${\displaystyle v_{i}}$, ${\displaystyle v_{j}}$y${\displaystyle v_{k}}$) asociado a las tres variables más un cuarto nodo auxiliar${\displaystyle v_{ijk}}$. ^{[ nota 1 ]} Un término ternario genérico puede reescribirse como la suma de una constante, tres términos unarios, tres términos binarios y un término ternario en forma simplificada. Puede haber dos casos diferentes, según el signo de${\displaystyle p=w_{ijk}(0,0,0)+w_{ijk}(0,1,1)+w_{ijk}(1,0,1)+w_{ijk}(1,1,0)}$. Si${\displaystyle p>0}$entonces

${\displaystyle w_{ijk}(x_{i},x_{j},x_{k})=w_{ijk}(0,0,0)+p_{1}(x_{i}-1)+p_{2}(x_{j}-1)+p_{3}(x_{k}-1)+p_{23}(x_{j}-1)x_{k}+p_{31}x_{i}(x_{k}-1)+p_{12}(x_{i}-1)x_{j}-px_{i}x_{j}x_{k}}$

con

${\displaystyle {\begin{aligned}p_{1}&=w_{ijk}(1,0,1)-w_{ijk}(0,0,1)\\p_{2}&=w_{ijk}(1,1,0)-w_{ijk}(1,0,1)\\p_{3}&=w_{ijk}(0,1,1)-w_{ijk}(0,1,0)\\p_{23}&=w_{ijk}(0,0,1)+w_{ijk}(0,1,0)-w_{ijk}(0,0,0)-w_{ijk}(0,1,1)\\p_{31}&=w_{ijk}(0,0,1)+w_{ijk}(1,0,0)-w_{ijk}(0,0,0)-w_{ijk}(1,0,1)\\p_{12}&=w_{ijk}(0,1,0)+w_{ijk}(1,0,0)-w_{ijk}(0,0,0)-w_{ijk}(1,1,0).\end{aligned}}}$

Si${\displaystyle p<0}$La construcción es similar, pero las variables tendrán valores opuestos. Si la función es regular, entonces todas sus proyecciones de dos variables serán submodulares, lo que implica que${\displaystyle p_{23}}$,${\displaystyle p_{31}}$y${\displaystyle p_{12}}$son positivos y entonces todos los términos en la nueva representación son submodulares.

En esta descomposición, los términos constante, unario y binario se pueden representar como se muestra en las secciones anteriores. Si${\displaystyle p>0}$El término ternario se puede representar con un gráfico de cuatro aristas.${\displaystyle v_{i}\rightarrow v_{ijk}}$,${\displaystyle v_{j}\rightarrow v_{ijk}}$,${\displaystyle v_{k}\rightarrow v_{ijk}}$,${\displaystyle v_{ijk}\rightarrow t}$, todos con peso${\displaystyle p}$, mientras que si${\displaystyle p<0}$El término puede representarse mediante cuatro aristas.${\displaystyle v_{ijk}\rightarrow v_{i}}$,${\displaystyle v_{ijk}\rightarrow v_{j}}$,${\displaystyle v_{ijk}\rightarrow v_{k}}$,${\displaystyle s\rightarrow v_{ijk}}$con peso${\displaystyle -p}$. ^{[ 8 ]}

Tras construir un grafo que representa una función pseudobooleana, es posible calcular un corte mínimo utilizando alguno de los diversos algoritmos desarrollados para redes de flujo, como los algoritmos de Ford-Fulkerson , Edmonds-Karp y Boykov-Kolmogorov . El resultado es una partición del grafo en dos componentes conexas.${\displaystyle S}$y${\displaystyle T}$de tal manera que${\displaystyle s\in S}$y${\displaystyle t\in T}$y la función alcanza su mínimo global cuando${\displaystyle x_{i}=0}$para cada${\displaystyle i}$de tal manera que el nodo correspondiente${\displaystyle v_{i}\in S}$, y${\displaystyle x_{i}=1}$para cada${\displaystyle i}$de tal manera que el nodo correspondiente${\displaystyle v_{i}\in T}$.

Los algoritmos de flujo máximo, como el de Boykov - Kolmogorov, son muy eficientes en la práctica para la computación secuencial, pero son difíciles de paralelizar, lo que los hace inadecuados para aplicaciones de computación distribuida e impide que aprovechen el potencial de las CPU modernas . Se desarrollaron algoritmos de flujo máximo paralelos, como push-relabel ^{[ 9 ]} y jump-flood ^{[ 1 ]} , que también pueden aprovechar la aceleración por hardware en implementaciones GPGPU . ^{[ 10 ] [ 1 ] [ 11 ]}

La construcción anterior permite la optimización global de funciones pseudobooleanas únicamente, pero puede extenderse a funciones cuadráticas de variables discretas con un número finito de valores, en la forma

${\displaystyle f(\mathbf {x} )=\sum _{i\in V}D(x_{i})+\sum _{(i,j)\in E}S(x_{i},x_{j})}$

dónde${\displaystyle E\subseteq V\times V}$y${\displaystyle x_{i}\in \Lambda =\{1,\dots ,k\}}$. La función${\displaystyle D(x_{i})}$representa la contribución unaria de cada variable (a menudo denominada término de datos ), mientras que la función${\displaystyle S(x_{i},x_{j})}$representa interacciones binarias entre variables ( término de suavidad ). En el caso general, la optimización de tales funciones es un problema NP-difícil , y los métodos de optimización estocástica como el recocido simulado son sensibles a los mínimos locales y en la práctica pueden generar resultados arbitrariamente subóptimos. ^{[ nota 2 ]} Con cortes de grafos es posible construir algoritmos de movimiento que permiten alcanzar en tiempo polinomial un mínimo local con fuertes propiedades de optimalidad para una amplia familia de funciones cuadráticas de interés práctico (cuando la interacción binaria${\displaystyle S(x_{i},x_{j})}$es una métrica o una semimétrica ), de modo que el valor de la función en la solución se encuentra dentro de un factor constante y conocido del óptimo global. ^{[ 12 ]}

Dada una función${\displaystyle f:\Lambda ^{n}\to \mathbb {R} }$con${\displaystyle \Lambda =\{1,\dots ,k\}}$y una determinada asignación de valores${\displaystyle \mathbf {x} =(x_{1},\dots ,x_{n})\in \Lambda ^{n}}$A las variables, es posible asociar cada asignación.${\displaystyle \mathbf {x} }$a una partición${\displaystyle P=\{P_{l}|l\in \Lambda \}}$del conjunto de variables, de tal manera que,${\displaystyle P_{l}=\{x_{i}|x_{i}=l\in \Lambda \}}$. Proporcione dos tareas distintas${\displaystyle P}$y${\displaystyle P'}$y un valor${\displaystyle \alpha \in \Lambda }$, una medida que transforma${\displaystyle P}$en${\displaystyle P'}$Se dice que es un${\displaystyle \alpha }$-expansión si${\displaystyle P_{\alpha }\subset P'_{\alpha }}$y${\displaystyle P'_{l}\subset P_{l}\;\forall l\in \Lambda -\{\alpha \}}$Dados un par de valores${\displaystyle \alpha }$y${\displaystyle \beta }$Se dice que una medida es${\displaystyle \alpha \beta }$-intercambiar si${\displaystyle P_{l}=P'_{l}\;\forall l\in \Lambda -\{\alpha ,\beta \}}$. Intuitivamente, un${\displaystyle \alpha }$-movimiento de expansión desde${\displaystyle \mathbf {x} }$asigna el valor de${\displaystyle \alpha }$a algunas variables que tienen un valor diferente en${\displaystyle \mathbf {x} }$, mientras que un${\displaystyle \alpha \beta }$-intercambiar mover asigna${\displaystyle \alpha }$a algunas variables que tienen valor${\displaystyle \beta }$en${\displaystyle \mathbf {x} }$y viceversa.

Para cada iteración, el${\displaystyle \alpha }$-el algoritmo de expansión calcula, para cada valor posible${\displaystyle \alpha }$, el mínimo de la función entre todas las asignaciones${\displaystyle \mathrm {A} (\mathbf {x} )}$que se puede alcanzar con un solo${\displaystyle \alpha }$-Ampliación de la solución temporal actual${\displaystyle \mathbf {x} }$y lo toma como la nueva solución temporal.

${\displaystyle \mathbf {x} :={\text{arbitrary value in }}\Lambda ^{n}}$${\displaystyle {\text{exit}}:=0}$mientras${\displaystyle {\text{exit}}\neq 1}$: ${\displaystyle {\text{exit}}=1}$para cada${\displaystyle \alpha \in \Lambda }$: ${\displaystyle \mathbf {\hat {x}} :=\arg \min _{\mathbf {y} \in \mathrm {A} (\mathbf {x} )}f(\mathbf {y} )}$si${\displaystyle f(\mathbf {\hat {x}} )<f(\mathbf {x} )}$: ${\displaystyle \mathbf {x} =\mathbf {\hat {x}} }$${\displaystyle {\text{exit}}:=0}$

El${\displaystyle \alpha \beta }$El algoritmo -swap es similar, pero busca el mínimo entre todas las asignaciones.${\displaystyle \mathrm {A} \mathrm {B} (\mathbf {x} )}$accesible con un solo${\displaystyle \alpha \beta }$-intercambiar movimiento de${\displaystyle \mathbf {x} }$.

${\displaystyle \mathbf {x} :={\text{arbitrary value in }}\Lambda ^{n}}$${\displaystyle {\text{exit}}:=0}$mientras${\displaystyle {\text{exit}}\neq 1}$: ${\displaystyle {\text{exit}}=1}$para cada${\displaystyle (\alpha ,\beta )\in \Lambda ^{2}}$: ${\displaystyle \mathbf {\hat {x}} :=\arg \min _{\mathbf {y} \in \mathrm {A} \mathrm {B} (\mathbf {x} )}f(\mathbf {y} )}$si${\displaystyle f(\mathbf {\hat {x}} )<f(\mathbf {x} )}$: ${\displaystyle \mathbf {x} =\mathbf {\hat {x}} }$${\displaystyle {\text{exit}}:=0}$

En ambos casos, el problema de optimización en el bucle más interno se puede resolver de forma exacta y eficiente mediante un corte de grafo. Ambos algoritmos finalizan con certeza en un número finito de iteraciones del bucle externo, y en la práctica dicho número es pequeño, produciéndose la mayor parte de la mejora en la primera iteración. Los algoritmos pueden generar diferentes soluciones dependiendo de la estimación inicial, pero en la práctica son robustos con respecto a la inicialización, y comenzar con un punto donde todas las variables tienen el mismo valor aleatorio suele ser suficiente para obtener resultados de buena calidad. ^{[ 12 ]}

La solución generada por dichos algoritmos no es necesariamente un óptimo global, pero tiene fuertes garantías de optimalidad. Si${\displaystyle S(x_{i},x_{j})}$es una métrica y${\displaystyle \mathbf {x} }$es una solución generada por el${\displaystyle \alpha }$-algoritmo de expansión, o si${\displaystyle S(x_{i},x_{j})}$es una semimétrica y${\displaystyle \mathbf {x} }$es una solución generada por el${\displaystyle \alpha \beta }$-algoritmo de intercambio, entonces${\displaystyle f(\mathbf {x} )}$se encuentra dentro de un factor conocido y constante del mínimo global${\displaystyle f(\mathbf {x} ^{*})}$: ^{[ 12 ]}

${\displaystyle f(\mathbf {x} )\leq 2{\frac {\max _{\alpha \neq \beta \in \Lambda }S(\alpha ,\beta )}{\min _{\alpha \neq \beta \in \Lambda }S(\alpha ,\beta )}}f(\mathbf {x} ^{*}).}$

En términos generales, el problema de optimizar una función pseudobooleana no submodular es NP-difícil y no puede resolverse en tiempo polinomial con un simple corte de grafo. El enfoque más sencillo consiste en aproximar la función con una similar pero submodular, por ejemplo, truncando todos los términos no submodulares o reemplazándolos con expresiones submodulares similares. Este enfoque suele ser subóptimo y solo produce resultados aceptables si el número de términos no submodulares es relativamente pequeño. ^{[ 13 ]}

En el caso de funciones cuadráticas no submodulares, es posible calcular en tiempo polinomial una solución parcial utilizando algoritmos como QPBO . ^{[ 13 ]} Las funciones de orden superior pueden reducirse en tiempo polinomial a una forma cuadrática que puede optimizarse con QPBO. ^{[ 14 ]}

Las funciones cuadráticas se han estudiado exhaustivamente y se han caracterizado en detalle, pero también se han obtenido resultados más generales para funciones de orden superior. Si bien las funciones cuadráticas pueden modelar muchos problemas de interés práctico, están limitadas por el hecho de que solo pueden representar interacciones binarias entre variables. La posibilidad de capturar interacciones de orden superior permite comprender mejor la naturaleza del problema y proporciona resultados de mayor calidad que serían difíciles de lograr con modelos cuadráticos. Por ejemplo, en aplicaciones de visión artificial , donde cada variable representa un píxel o vóxel de la imagen, las interacciones de orden superior pueden utilizarse para modelar información de textura, que sería difícil de capturar utilizando únicamente funciones cuadráticas. ^{[ 15 ]}

Se desarrollaron condiciones suficientes análogas a la submodularidad para caracterizar funciones pseudobooleanas de orden superior que pueden optimizarse en tiempo polinomial, ^{[ 16 ]} y existen algoritmos análogos a${\displaystyle \alpha }$-expansión y${\displaystyle \alpha \beta }$-intercambio para algunas familias de funciones de orden superior. ^{[ 15 ]} El problema es NP-difícil en el caso general, y se desarrollaron métodos aproximados para la optimización rápida de funciones que no satisfacen tales condiciones. ^{[ 16 ] [ 17 ]}

• Boykov, Yuri; Veksler, Olga; Zabih, Ramin (2001). "Minimización rápida aproximada de energía mediante cortes de grafos". IEEE Transactions on Pattern Analysis and Machine Intelligence . 23 (11): 1222– 1239. Bibcode : 2001ITPAM..23.1222B . CiteSeerX 10.1.1.439.2071 . doi : 10.1109/34.969114 . 
• Freedman, Daniel; Drineas, Petros (2005). Minimización de energía mediante cortes de grafos: Determinando lo que es posible (PDF) . Conferencia de la IEEE Computer Society sobre Visión por Computadora y Reconocimiento de Patrones. Vol.  2. pp. 939–946 . 
• Goldberg, Andrew V; Tarjan, Robert E (1988). "Un nuevo enfoque al problema del flujo máximo" (PDF) . Journal of the ACM . 35 (4): 921– 940. doi : 10.1145/48014.61051 . S2CID 52152408 . 
• Ishikawa, Hiroshi (2014). Reducción de cliques de orden superior sin variables auxiliares (PDF) . Conferencia IEEE sobre visión por computadora y reconocimiento de patrones. IEEE. pp. 1362–1369 . 
• Hong, Li; Chen, George (2004). Segment-based stereo matching using graph cuts (PDF) . Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol.  1. pp. 74–81 . 
• Kohli, Pushmeet; Kumar, M. Pawan; Torr, Philip HS (2009). "P ³ & Beyond: Move Making Algorithms for Solving Higher Order Functions" ( PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 31 (9): 1645– 1656. doi : 10.1109/tpami.2008.217 . PMID 19574624. S2CID 91470 .  
• Kim, Junhwan; Kolmogorov, Vladimir; Zabih, Ramin (2003). Correspondencia visual mediante minimización de energía e información mutua . Actas de la Novena Conferencia Internacional IEEE sobre Visión por Computadora. pp. 1033–1040 . doi : 10.1109/ICCV.2003.1238463 . 
• Kohli, Pushmeet; Ladicky, Lubor; Torr, PHS (2008). Cortes de grafos para minimizar potenciales robustos de orden superior (PDF) (Informe técnico). Universidad Oxford Brookes. págs. 1–9 . 
• Kolmogorov, Vladimir; Rother, Carsten (2007). "Minimizing Nonsubmodular Functions: A Review". IEEE Transactions on Pattern Analysis and Machine Intelligence . 29 (7): 1274– 1279. doi : 10.1109/tpami.2007.1031 . PMID 17496384 . S2CID 15319364 .  
• Kolmogorov, Vladimir; Zabin, Ramin (2004). "¿Qué funciones de energía se pueden minimizar mediante cortes de grafos?" (PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 26 (2): 1645– 1656. Bibcode : 2004ITPAM..26..147K . doi : 10.1109/TPAMI.2004.1262177 . hdl : 1813/5842 . PMID 15376891 . 
• Lombaert, Herve; Cheriet, Farida (2012). Eliminación simultánea de ruido y registro de imágenes mediante cortes de grafos: Aplicación a imágenes médicas corruptas (PDF) . XI Conferencia Internacional sobre Ciencias de la Información, Procesamiento de Señales y sus Aplicaciones. pp. 264–268 . 
• Peng, Yi; Chen, Li; Ou-Yang, Fang-Xin; Chen, Wei; Yong, Jun-Hai (2015). "JF-Cut: un enfoque de corte de grafos paralelo para imágenes y videos a gran escala". IEEE Transactions on Image Processing . 24 (2): 655– 666. Bibcode : 2015ITIP...24..655P . doi : 10.1109/TIP.2014.2378060 . PMID 25494510 . S2CID 1665580 .  
• Rother, Carsten; Kolmogorov, Vladimir; Blake, Andrew (2004). Grabcut: Extracción interactiva de primer plano mediante cortes de grafos iterados (PDF) . Transacciones ACM sobre gráficos. Vol.  23. pp. 309–314 . 
• So, Ronald WK; Tang, Tommy WH; Chung, Albert CS (2011). "Registro no rígido de imágenes de resonancia magnética cerebral mediante cortes de grafos". Pattern Recognition . 44 ( 10– 11): 2450– 2467. Bibcode : 2011PatRe..44.2450S . doi : 10.1016/j.patcog.2011.04.008 .
• Stich, Timo (2009). Cortes de grafos con CUDA (PDF) . Conferencia de tecnología GPU.
• Tang, Tommy WH; Chung, Albert CS (2007). Registro de imágenes no rígido mediante cortes de grafos (PDF) . Conferencia Internacional sobre Computación de Imágenes Médicas e Intervención Asistida por Computadora. pp. 916–924 . doi : 10.1007/978-3-540-75757-3_111 . 
• Vineet, Vibhav; Narayanan, PJ (2008). CUDA cuts: Cortes rápidos de grafos en la GPU (PDF) . Talleres de la Conferencia de la Sociedad de Computación IEEE sobre Visión por Computadora y Reconocimiento de Patrones. págs. 1–8 . 

• Implementación (C++) de varios algoritmos de corte de grafos de Vladimir Kolmogorov.
• GCO , biblioteca de optimización de cortes de grafos creada por Olga Veksler y Andrew Delong.