Mostrar código-fonte de Partição de grafos

Em [[matemática]], o problema de '''partição de grafos''' é definido com seus dados na forma de um [[grafo (matemática)|grafo]] ''G'' = (''V'',''A''), com ''V'' vértices e ''A'' arestas, de tal modo que é possível [[particionar um conjunto|particionar]] ''G'' em componentes menores com propriedades específicas. Por exemplo, uma partição de ''k''-vias divide o conjunto de vértices em ''k'' componentes menores. Uma boa partição é definida como uma em que o número de arestas entre componentes menores é pequeno. Partição Uniforme de um Grafo é um tipo de problema de particionamento de grafo que consiste em dividir um grafo em componentes, no qual os componentes são quase do mesmo tamanho e existem algumas conexões entre esses componentes. Importantes aplicações de particionamento de grafos incluem computação específica, particionando vários estágios de um circuito feito em [[VSLI]] e agendamento de tarefas em sistemas com multi-processadores.<ref name="balgraph">
{{citar periódico
 |autor = Andreev, Konstantin and Räcke, Harald,
 |título= Balanced Graph Partitioning
 |periódico= Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures
 |ano= 2004
 |local= Barcelona, Spain
 |páginas= 120–124
 | doi = 10.1145/1007912.1007931
 | isbn = 1-58113-840-7
 }}</ref> Recentemente, o problema de partição de grafo ganhou importância devido à suas aplicações para clustering e detecção de associações em redes sociais, patológicas e biológicas. Uma pesquisa sobre as recentes tendências em métodos e aplicações computacionais podem ser encontrados em.<ref name="recentadvances">
{{citar periódico
 |autor = Aydin Buluc and Henning Meyerhenke and Ilya Safro and Peter Sanders and Christian Schulz
 |título= Recent Advances in Graph Partitioning
 | url = http://arxiv.org/abs/1311.3144
 |ano= 2013
 |páginas= 36
}}</ref>

== Problema da Complexidade ==

Geralmente, problemas de partição de grafos estão dentro da categoria dos problemas NP-Difíceis. Soluções para esses problemas são geralmente derivadas usando algoritmos de heurísticas de aproximação.<ref name=baltrees>
{{citar periódico
 |autor = Feldmann, Andreas Emil and Foschini, Luca
 |título= Balanced Partitions of Trees and Applications
 |periódico= Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science
 |ano= 2012
 |local= Paris, France
 |páginas= 100–111
 }}</ref> Entretanto, o particionamento uniforme de um grafo ou particionamento equilibrado pode ser mostrado com uma aproximação NP-Completa com qualquer fator finito.<ref name=balgraph /> Até para classes especiais de grafos como árvores e redes, não existem algoritmos de aproximação razoáveis<ref name="fastpartition">
{{citar periódico
 |autor = Feldmann, Andreas Emil
 |título= Fast Balanced Partitioning is Hard, Even on Grids and Trees
 |periódico= Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science
 |ano= 2012
 |local= Bratislava, Slovakia
 }}</ref> a menos que P=NP. Redes são uma particularidade interessante visto que modelam um grafo resultante de simulações do [[Método dos elementos finitos|Método dos elementos finitos (MEF)]]. Quando não apenas o número de áreas entre componentes é próximo, mas também o tamanho dos componentes, é mostrado que não existe nenhum algoritmo polinomial razoável para estes tipos de grafos.<ref name="fastpartition" />

==Problema==
Considere um grafo ''G'' = (''V'', ''A''), onde ''V'' é o conjunto de ''n'' vértices e ''A'' o conjunto de arestas. Para um problema (''k'',''v'') de partição balanceada, o objetivo é particionar ''G'' em ''k'' componentes de tamanho máximo ''v''&middot;(''n''/''k''), enquanto minimiza a capacidade das arestas entre elementos separados.<ref name=balgraph /> Também, dado o ''G'' e um inteiro ''k'' > 1, divida ''V'' em ''k'' partes (subconjuntos) ''V''<sub>1</sub>, ''V''<sub>2</sub>, ..., ''V<sub>k</sub>'' sendo que essas partes devem ser disjuntas e ter o mesmo tamanho, e o número de arestas com pontos finais em diferentes partes é minimizado. Tais problemas de partições foram discutidos na literatura como aproximação de duplo critério ou abordagem de aproximação de recursos. Uma extensão comum são os [[hipergrafo]]s, onde uma aresta pode conectar mais de dois vértices. Uma hiperaresta não é cortada se todos os vértices estão na mesma partição, e cortadas exatamente uma vez caso contrário, não importando quantos vértices estão em cada lado. Esse tipo de uso é comum em [[automação de design eletrônico]].

===Análise===
Para um problema específico balanceado (''k'', 1&nbsp;+&nbsp;''ε''), procuramos encontrar o custo mínimo da partição de ''G'' em ''k'' elementos com cada componente contendo o máximo de (1&nbsp;+&nbsp;''ε'')&middot;(''n''/''k'') nós. Comparamos os custos desse algoritmo de aproximação ao custo de (''k'',1) cortes, em que cada um dos ''k'' componentes devem ter exatamente o mesmo tamanho de  (''n''/''k'') nós cada, sendo, assim, um problema mais restrito. Todavia,

: <math>\max_i |V_i| \le (1+\varepsilon) \left\lceil\frac{|V|}{k}\right\rceil.</math>

Já sabemos que o corte (2,1) é o corte mínimo do problema da bisseção e este é [[NP-completo|NP-Completo]].<ref name="minbisect">
{{citar livro
 |autor = Garey, Michael R. and Johnson, David S.
 |título= Computers and intractability: A guide to the theory of NP-completeness
 |ano= 1979
 | isbn = 0-7167-1044-7
 |publicado= W. H. Freeman & Co.
}}</ref> Em seguida, avaliamos um problema 3-partições no qual ''n''&nbsp;=&nbsp;3''k'', que também é limitado em tempo polinomial.<ref name=balgraph /> Agora, se assumirmos que temos um algoritmo de aproximação finita para (''k'',&nbsp;1)-partições equilibradas, então, cada uma das instancias da 3-partição pode ser resolvida usando a partição balanceada (''k'',1) em ''G'' ou não pode ser resolvida. Se a instância de 3-partição pode ser resolvida então o problema do (''k'',&nbsp;1)-particionamento balanceado em ''G'' pode ser resolvido sem cortar nenhuma aresta. Entretanto, se a instância 3-partição não pode ser resolvida, o (''k'', 1)-paticionamento balanceado ideal em ''G'' vai cortar pelo menos uma aresta. Um algoritmo de aproximação com fator de aproximação finito tem de diferenciar entre estes dois casos. Assim, pode-se resolver o problema da 3-partição no qual há uma contradição quando assume-se que ''P''&nbsp;=&nbsp;''NP''. Entretanto, é evidente que um problema de (''k'',1)-particionamento balanceados não tem algoritmo de aproximação em tempo polinomial com fator de aproximação finito a menos que ''P''&nbsp;=&nbsp;''NP''.<ref name=balgraph />

O [[teorema separador de planos]] diz que qualquer ''n''-vértice do [[grafo planar]] pode ser particionado em  partes aproximadamente iguais com a remoção de O(√''n'') vértices. Esta não é uma partição no sentido descrito anteriormente, porque a partição é nos vértices e não nas arestas. Porém, o mesmo resultado implica que cada grafo planar de of grau limitado tem um equilíbrio de corte com O(√''n'') arestas.

==Métodos de partição de Grafos==
Visto que o problema de particionamento de grafos é um problema difícil, soluções práticas são baseadas em heurísticas.  Existem duas heurísticas principais, local e global. Métodos locais bem conhecidos são os [[Kernighan–algoritmos de Lin|algoritmos de Kernighan–Lin]], e [[algoritmos de Fiduccia-Mattheyses]], que são os primeiros algoritmos 2-vias de corte que são eficientes usando estratégias de busca locais. A sua principal desvantagem é o particionamento inicial arbitrário do conjunto vértice, que pode afetar a qualidade final da solução.  A aproximação global dependem de propriedades do grafo inteiro e não só de uma partição arbitrária inicial. O exemplo mais conhecido é o espectro de partição, onde uma partição é derivada de um espectro de matrizes de adjacência.

==Métodos de multi-nível==
Um algoritmo de particionamento de grafos multi-nível funciona aplicando um ou mais estágios.  Cada estágio reduz o tamanho de um grafo por pela eliminação de vértices e arestas, divisórias no grafo menor, em seguida, mapeia novamente e refina esta partição do grafo original.<ref>
{{citar conferência
 |título=A multilevel algorithm for partitioning graphs
  |autor =Hendrickson, B. and Leland, R.
  |conferencia=Proceedings of the 1995 ACM/IEEE conference on Supercomputing
  |páginas=28
  |ano=1995
  |publicado=ACM
}}</ref>  Uma grande variedade de métodos de particionamento e refinamento pode ser aplicado no conjunto do sistema multi-nível.  Em muitos casos, esta aproximação pode nos dar tempo de execução mais rápido e resultados de alta qualidade.
Um exemplo que é muito utilizado dessa aproximação é o [[METIS]],<ref name=":0">{{citar periódico
 |título=A fast and high quality multilevel scheme for partitioning irregular graphs
 |autor =Karypis, G. and Kumar, V.
 |periódico=SIAM Journal on Scientific Computing
 |volume=20
 |número=1
 |páginas=359
 |ano=1999
 |doi=10.1137/S1064827595287997
}}</ref> um particionador de grafos, e o hMETIS, o mesmo particionador mas para hipergrafos.<ref name="hmetis">
{{citar conferência
 |título=Multilevel hypergraph partitioning: application in VLSI domain
 |autor =Karypis, G. and Aggarwal, R. and Kumar, V. and Shekhar, S.
 |títulolivro=Proceedings of the 34th annual Design Automation Conference
 |páginas=526–529
 |ano=1997
}}</ref>

==Particionamento de espectro e espectro de bisseção==
Dado um grafo com a [[matriz de adjacência]] ''A'', onde uma entrada ''A<sub>ij</sub>'' implica uma aresta entre os nós ''i'' e ''j'', e a [[Matriz de Nível|matriz de nível]] ''D'', que é uma matriz diagonal, onde cada entrada na diagonal de uma linha ''i'', ''d<sub>ii</sub>'', representa o grau/nível de um nó ''i''. A [[Matriz de Laplace]] ''L'' é definida como ''L''&nbsp;=&nbsp;''D''&nbsp;&minus;&nbsp;''A''. Agora, uma partição na proporção de corte de ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'') é definida como uma partição de ''V'' na disjunção ''U'', e ''W'', de tal modo que o custo de corte (''U'',''W'')/(|''U''|&middot;|''W''|) é minimizado.

Em tal cenário, o segundo menor [[autovalor]] (''λ'') de ''L'', produz um limite inferior para o custo ótimo (''c'') de partição de corte com relação ''c''&nbsp;≥&nbsp;''λ''/''n''. O [[autovetor]] (''V'') correspondente à ''λ'', chamado de vetor de Fiedler, bissecciona o grafo em apenas duas comunidades baseadas no sinal da entrada do vetor correspondente. Dividindo em um número maior de comunidades é geralmente atingido ao fazendo bisseções repetidas, mas nem sempre isso dá resultados satisfatórios. Os exemplos nas figuras 1 e 2 mostram o espectro de bisseção.

[[File:Bisected network.jpg|thumb|Figura 1: O grafo ''G''&nbsp;=&nbsp;(5,4) é analisado com bisseção espectral. A combinação linear dos dois menores autovetores leva a [1 1 1 1 1]' possuindo um autovalor&nbsp;=&nbsp;0.]]

[[Imagem:Connected graph..jpg|thumb|Figura 2: O grafo ''G''&nbsp;=&nbsp;(5,5) ilustra que o vetor de Fiedler em vermelho corta o grafo em duas comunidades, uma com vértices {1,2,3} com entradas positivas no espaço vetorial, e outra comunidade tem vértices {4,5} com entradas de espaço de vetor negativos.]]

Particionamento mínimo corte no entanto falha quando o número de comunidades a ser particionado, ou o tamanho das partições são desconhecidas. Por exemplo, otimizando o tamanho do corte para grupos de tamanho qualquer coloca todos os vértices na mesma comunidade. Além disso, o tamanho do corte pode ser a coisa errada a minimizar uma vez que uma boa divisão não é apenas aquele com pequeno número de arestas entre as comunidades.  Isso motivou o uso da [[Modularidade (redes)|Modularidade]] (Q) <ref name="npnas">
{{citar periódico
 |autor = Newman, M. E. J.
 |ano= 2006
 |título= Modularity and community structure in networks
 |periódico= PNAS
 | volume = 103
 |número= 23
 |páginas= 8577–8696
 | doi = 10.1073/pnas.0601602103
 | pmid=16723398
 | pmc=1482622
}}</ref> como uma métrica para otimizar e balancear uma partição de grafo. O exemplo na figura 3 ilustra 2 instâncias do mesmo grafo de modo que em ''(a)'' modularidade (Q) representa a métrica de particionamento e em ''(b)'', proporção de corte representa a métrica de particionamento. Entretanto, sabe-se que  Q sofre um limite de resolução, produzindo resultados duvidosos quando está lidando com comunidades pequenas. Neste contexto, [[Surprise (redes)|Surprise]]<ref name = "Surprise">
{{citar periódico
 |autor = Rodrigo Aldecoa and Ignacio Marín
 |ano= 2011
 |título= Deciphering network community structure by Surprise
 |periódico= PLoS ONE
 | volume = 6
 |número= 9
 |páginas= e24195
 | doi = 10.1371/journal.pone.0024195
 | pmid = 21909420
 | url = http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0024195
 | pmc=3164713
}}
</ref> foi proposta como uma alternativa de aproximação para a avaliação de qualidade de uma partição.

[[Imagem:Graph comparison.jpg|thumb|Figura 3: Grafo ponderado ''G'' pode ser particionado para maximizar ''Q'' em (a) ou para minimizar a proporção de corte em (b). Nós vemos que (a) é uma melhor partição balanceada, motivando, assim, a importância da modularidade em problemas de particionamento de grafos.]]

==Outros métodos de partição==
Modelos de spin têm sido usados para o agrupamento de dados multivariados que similaridades são convertidas em forças de acoplamento.<ref name="potts">
{{citar periódico
 |título= Statistical mechanics of community detection
 |data=julho de 2006
 | doi = 10.1103/PhysRevE.74.016110
 |autor = Reichardt, Jörg and Bornholdt, Stefan
 |número= 1
 |periódico= Phys. Rev. E
 |páginas= 016110
 | volume = 74
}}</ref> As propriedades de configuração de spin do [[estado fundamental]] pode ser diretamente interpretado como comunidades. Entretanto, um grafo é particionado para minimizar o Hamiltoniano do grafo particionado. O [[Mecânicas Hamiltonianas|Hamiltoniano]] (H) é derivado por atribuindo as seguintes recompensas partição e penalidades.
* Recompensas para arestas internas entre nós do mesmo grupo (mesmo spin)
* Penaliza arestas que faltam no mesmo grupo
* Penaliza arestas existentes entre diferentes grupos
* Recompensar a falta de ligações entre os diferentes grupos.

Adicionalmente, clusterings baseados em Kernel PCA tomam a forma de mínimos quadrados com suporte ao [[framework]] Vector Machine, e, portanto, torna-se possível projetar as entradas de dados para um espaço de características do kernel induzida que tem variação máxima, implicando, assim, uma alta de separação entre as comunidades projetadas <ref name="pami">
{{citar periódico
 |autor = Carlos Alzate and Johan A.K. Suykens
 |título= Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA
 |periódico= IEEE Transactions on Pattern Analysis and Machine Intelligence
 | volume = 32
 | issn = 0162-8828
 |ano= 2010
 |páginas= 335–347
 | doi=10.1109/TPAMI.2008.292
 |publicado= IEEE Computer Society
 |número= 2
 | pmid = 20075462
}}</ref>

Alguns métodos expressam o particionamento de grafo como um problema de otimização multi-critérios que podem ser resolvidos através de métodos locais expressos em um framework teórico de jogo onde cada nó faz uma decisão sobre a partição que ele escolhe.<ref>Kurve, Griffin, Kesidis (2011) "A graph partitioning game for distributed simulation of networks" Proceedings of the 2011 International Workshop on Modeling, Analysis, and Control of Complex Networks: 9 -16</ref>

== Ferramentas de Software ==

Um dos primeiros{{carece de fontes|data=dezembro de 2013}} pacotes de software disponibilizados ao público é chamado Chaco<ref name="chaco">
{{citar periódico
 |autor = Bruce Hendrickson
 |título= Chaco: Software for Partitioning Graphs
 }}</ref>  devido à Hendrickson e Leland.
Como a maioria dos pacotes de software disponíveis publicamente,{{carece de fontes|data=dezembro de 2013}} Chaco implementa a abordagem a vários níveis descritos acima e básicos algoritmos de busca local.
Além disso, implementar técnicas de separação espectral.

[[METIS]]<ref name=":0"/> é um grafo de particionamento conhecido, criado por Karypis and Kumar.
kMetis é focado{{weasel-inline|date=dezembro de 2013}}  em particionamento rápido e hMetis,<ref name="hmetis"/> que é um particionador de hipergrafos, visa a qualidade de particionamento. {{weasel-inline|date=dezembro de 2013}}
ParMetis<ref name=":0"/> é uma implementação paralela do algoritmo de particionamento de grafos Metis.

PaToH<ref name="patoh">{{citar conferência
 |autor = Ü. Catalyürek and C. Aykanat
 |título= PaToH: Partitioning Tool for Hypergraphs
 |ano=2011
 }}</ref>  é também largamente utilizado {{carece de fontes|data=dezembro de 2013}} como particionador de hipergrafos que produz partições de alta qualidade{{carece de fontes|data=dezembro de 2013}}.

Scotch<ref name="scotch">{{citar periódico
 |autor = C. Chevalier and F. Pellegrini
 |título= PT-Scotch: A Tool for Efficient Parallel Graph Ordering
 |periódico= Parallel Computing
 | volume = 34
 |número= 6
 |páginas= 318–331
 |ano=2008
 | doi=10.1016/j.parco.2007.12.001
 }}</ref> é um framework de grafos criado por Pellegrini. Ele usa bisseção recursiva multinível e inclui sequencial, bem como técnicas de separação paralelas.

Jostle<ref name="jostle">{{citar periódico
 |autor = C. Walshaw and M. Cross
 |título= Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm
 |periódico= Journal on Scientific Computing
 | volume = 22
 |número= 1
 |páginas= 63–80
 |ano=2000
 | doi=10.1137/s1064827598337373
 }}</ref> é um particionamento grafo sequencial e paralelo solver desenvolvido por Chris Walshaw.
a versão comercializada dele é conhecida como NetWorks.

Se um modelo de rede de comunicação está disponível, então Jostle e Scotch são capazes de construir este modelo levando em consideração o processo de particionamento.{{carece de fontes|data=dezembro de 2013}}

Party<ref name="party">{{citar periódico
 |autor = R. Diekmann, R. Preis, F. Schlimbach and C. Walshaw
 |título= Shape-optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM
 |periódico= Parallel Computing
 | volume = 26
 |número= 12
 |páginas= 1555–1581
 |ano=2000
 | doi=10.1016/s0167-8191(00)00043-0
 }}</ref> implementa a o framework Bubble/shape-optimized e o algoritmo de Conjuntos Úteis.

O pacote de software DibaP<ref name="dibap">{{citar periódico
 |autor = H. Meyerhenke and B. Monien and T. Sauerwald
 |título= A New Diffusion-Based Multilevel Algorithm for Computing Graph Partitions
 |periódico= Journal of Parallel Computing and Distributed Computing
 | volume = 69
 |número= 9
 |páginas= 750–761
 |ano=2008
 | doi=10.1016/j.jpdc.2009.04.005
 }}</ref>  e seu variante MPI-parallelo PDibaP<ref name="pdibap">{{citar conferência
 |autor = H. Meyerhenke
 |título= Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations.
 |títulolivro= 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering
 |páginas= 67–82
 |ano=2013
 }}</ref> por Meyerhenke implementar o framework Bubble usando difusão; DibaP também usa técnicas baseadas em AMG para fortalicer e resolver sistemas lineares que surgem na abordagem difusiva.

Sanders e Schulz divulgou um pacote de particionamento de grafos chamado KaHIP<ref name="kahip">{{citar conferência
 |autor = P. Sanders and C. Schulz
 |título= Engineering Multilevel Graph Partitioning Algorithms
 |títulolivro= Proceeings of the 19th European Symposium on Algorithms (ESA)
 | volume = 6942
 |páginas= 469–480
 |ano=2011
 }}</ref> (Karlsruhe High Quality Partitioning) forcando em soluções da qualidade.{{peacock-term|date=dezembro de 2013}} Ele implementa por exemplo métodos baseados em fluxos, pesquisas locais mais localizada, e várias meta-heurísticas paralelas e sequenciais.

Para resolver o problema de [[balanceamento de carga]] em aplicações paralelas, versões distribuídas dos particionadores sequenciais Metis, Jostle e Scotch têm sido desenvolvidos. {{carece de fontes|data=dezembro de 2013}}

As ferramentas Parkway<ref name="parkway">{{citar periódico
 |autor = A. Trifunovic and W. J. Knottenbelt
 |título= Parallel Multilevel Algorithms for Hypergraph Partitioning
 |periódico= Journal of Parallel and Distributed Computing
 | volume = 68
 |número= 5
 |páginas= 563–581
 |ano=2008
 | doi=10.1016/j.jpdc.2007.11.002
 }}</ref> por Trifunovic e
Knottenbelt e também Zoltan<ref name="zoltan">{{citar conferência
 |autor = K. Devine and E. Boman and R. Heaphy and R. Bisseling and Ü. Catalyurek
 |título= Parallel Hypergraph Partitioning for Scientific Computing
 |títulolivro= Proceedings of the 20th International Conference on Parallel and Distributed Processing
 |páginas= 124-124
 |ano=2006
 }}</ref> por Devine et al. focam em particionamento de
hipergrafos.

'''Lista de frameworks de código aberto grátis:'''
{| class="wikitable"
|-
!Npme
!Licença
!Breve Descrição
|-
|Chaco||GPL|| pacote de software da implementação de técnicas espectrais e a abordagem multinível
|-
|DiBaP||*|| particionamento gráfico baseado em técnicas de vários níveis, algébrica multigrid, bem como gráfico baseado difusão
|-
|Jostle||*|| técnicas multinível de separação e difusão de balanceamento de carga, seqüencial e paralelo
|-
|KaHIP||GPL|| várias meta-heurísticas paralelas e seqüenciais, garante a limitação de equilíbrio
|-
|kMetis||Apache 2.0||pacote de particionamento de grafos com base em técnicas de vários níveis e k-vias de busca local
|-
|Mondriaan||LGPL|| particionador de matriz para particionar matrizes esparsas retangulares
|-
|PaToH||BSD|| particionamento multi-nível de hipergrafos
|-
|Parkway||*|| particionamento hipergrafo multinível paralelo
|-
|Scotch||CeCILL-C|| implementa bisseção recursiva multinível, bem como técnicas de difusão, seqüencial e paralelo
|-
|Zoltan||BSD|| particionamento de hipergrafo
|}

{{Referências}}

== Ligações externas ==
* Chamberlain, Bradford L. (1998). [http://homes.cs.washington.edu/~bradc/cv/pubs/degree/generals.pdf "Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations"]

== Bibliografia ==
* {{citar livro|título=Graph Partitioning: Optimisation and Applications|autor =Charles-Edmond Bichot, Patrick Siarry|ano=2011|publicado=ISTE – Wiley|isbn=978-1848212336|páginas=384|url=http://cebichot.netne.net/graph_partitioning_book/}}
* {{citar livro|último=Feldmann|primeiro=Andreas Emil|título=Balanced Partitioning of Grids and Related Graphs: A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations|ano=2012|publicado=Cuvillier Verlag|local=Goettingen, Germany|isbn=978-3954041251|páginas=218|url=http://www.pw.ethz.ch/people/research_group/andemil/personal/thesis.pdf}}{{Ligação inativa|1=data=maio de 2019 }} An exhaustive analysis of the problem from a theoretical point of view.
* {{citar periódico |título=An efficient heuristic procedure for partitioning graphs |url=http://www.ece.wisc.edu/~adavoodi/teaching/756-old/papers/kl.pdf |autor=BW Kernighan, S Lin |periódico=Bell System Technical Journal |ano=1970 |acessodata=2014-08-09 |arquivourl=https://web.archive.org/web/20120302175058/http://www.ece.wisc.edu/~adavoodi/teaching/756-old/papers/kl.pdf |arquivodata=2012-03-02 |urlmorta=yes }}  One of the early fundamental works in the field.  However, performance is O(n<sup>2</sup>), so it is no longer commonly used.
* {{citar conferência|título=A Linear-Time Heuristic for Improving Network Partitions |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1585498 |autor =CM Fiduccia, RM Mattheyses |títulolivro=Design Automation Conference |ano=1982}}  A later variant that is linear time, very commonly used, both by itself and as part of multilevel partitioning, see below.
* {{citar periódico|título=A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs |url=http://glaros.dtc.umn.edu/gkhome/node/107 |autor = G Karypis, V Kumar |periódico=Siam Journal on Scientific Computing |ano=1999}}  Multi-level partitioning is the current state of the art. This paper also has good explanations of many other methods, and comparisons of the various methods on a wide variety of problems.
* {{citar periódico|título=Multilevel hypergraph partitioning: applications in VLSI domain |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=748202 |autor = Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. |periódico=IEEE Transactions on Very Large Scale Integration (VLSI) Systems |data=março de 1999 |volume=7 |número=1 |páginas= 69–79 |doi=10.1109/92.748202}}  Graph partitioning (and in particular, hypergraph partitioning) has many applications to IC design.
* {{citar periódico|título=Optimization by Simulated Annealing |url=http://www.sciencemag.org/cgi/content/abstract/220/4598/671 |autor =S. Kirkpatrick, C. D. Gelatt Jr.,  and M. P. Vecchi |periódico=Science |data=13 de maio de 1983 |número=4598 |páginas=671–680 |doi= 10.1126/science.220.4598.671 |volume=220 |pmid=17813860}}  Simulated annealing can be used as well.
* {{citar periódico|título=New spectral methods for ratio cut partitioning and clustering |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=159993 |autor =Hagen, L. and Kahng, A.B. |periódico=IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |data=setembro de 1992 |volume=11,&nbsp; |número=9 |páginas= 1074–1085 |doi=10.1109/43.159993}}.  There is a whole class of ''spectral partitioning'' methods, which use the Eigenvectors of the Laplacian of the connectivity graph.  You can see [http://www.stanford.edu/~dgleich/demos/matlab/spectral/spectral.html a demo of this], using Matlab.

[[Categoria:Teoria dos grafos]]
[[Categoria:Complexidade]]