K-corte mínimo

Em matemática, o k-corte mínimo é o problema de otimização combinatória que requer encontrar um conjunto de arestas cuja remoção dessas arestas iria particionar o grafo em k componentes conexos. Essas arestas são chamadas de k-corte. O objetivo é encontrar o k-corte de peso mínimo. Esse particionamento pode ter aplicações em design VLSI, mineração de dados, elementos finitos e comunicação em computação paralela.

Definição formal

Dado um grafo não direcionado G = (V, E) com atribuição de pesos nas arestas w: E → N e um inteiro k ∈ {2, 3, …, |V|}, particione V em k conjuntos disjuntos F = {C₁, C₂, …, C_k} enquanto minimizando

$\sum _{i=1}^{k-1}\sum _{j=i+1}^k\sum _{\begin{array}{c}{v}_1\in C_i\\ v_2\in C_j\end{array}}w(\{v_1,v_2\})$

Para um k fixo, esse problema é solúvel em tempo polinomial de O(|V|^k2). No entanto, o problema é NP-completo se k for parte da entrada. Também é NP-completo se especificarmos $k$ vértices e pedirmos para o k-corte mínimo que separa esses vértices entre cada um dos conjuntos.

Ver também

• Corte máximo
• Corte mínimo

Referências

• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citar conferência