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{smallmatrix}v_{1}\in C_{i}\\v_{2}\in C_{j}\end{smallmatrix}}w(\left\{v_{1},v_{2}\right\})$

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

• Goldschmidt, O.; Hochbaum, D. S. (1988), Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, pp. 444–451 
• Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN 0-7167-1044-7, W.H. Freeman 
• Saran, H.; Vazirani, V. (1991), «Proc. 32nd Ann. IEEE Symp. on Foundations of Comput. Sci», IEEE Computer Society, Finding k-cuts within twice the optimal, pp. 743–751 
• Vazirani, Vijay V. (2003), Approximation Algorithms, ISBN 3-540-65367-8, Berlin: Springer 
• Guttmann-Beck, N.; Hassin, R. (1999), «Algorithmica», Approximation algorithms for minimum k-cut, pp. 198–207 
• Comellas, Francesc; Sapena, Emili (2006), «Cópia arquivada», Algorithmica, ISSN 0302-9743, 3907 (2): 279–285, doi:10.1007/s004530010013, consultado em 14 de dezembro de 2015, cópia arquivada em  🔗 
• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), «A Compendium of NP Optimization Problems», Minimum k-cut 
• Fernandez de la Vega, W.; Karpinski, M.; Kenyon, C. (2004). «Approximation schemes for Metric Bisection and partitioning». Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete Algorithms. pp. 506–515,