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|^k²).[1] No entanto, o problema é NP-completo se k for parte da entrada.[2] 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.[3]

Ver também

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 |contribution-url= ignorado (ajuda)
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 |contribution-url= ignorado (ajuda)
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 |arquivourl= requer |arquivodata= (ajuda) 🔗
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,

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Goldschmidt & Hochbaum 1988.

[2] Garey & Johnson 1979

[3] , which cites