Buscar

Problemas_extremais_em_grafos_usando_VNS

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 3, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 6, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 9, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Prévia do material em texto

Problemas extremais em grafos usando VNS
Rafael L. de Paula1
1Instituto Militar de Engenharia (IME) - Seção de Engenharia da Computação
Inteligência Artificial (IA) - Professores: Ronaldo e Duarte
Urca – RJ – Brasil
paula.rafael@ime.eb.br
Abstract. This work is a discipline of Artificial Intelligence, the requirement is
exact of our discipline of the maximal cut its mathematical and computational
approaches, and its approach meta one of the possible solutions not of this pro-
blem. The work makes a conceptual introduction, review of related works and
presents the results of the experiments carried out.
Resumo. Este trabalho é requisito da disciplina de Inteligência Artificial, nele é
abordado o problema do corte maximal, suas abordagens matemática e compu-
tacional, e sua abordagem meta-heurı́stica com o VNS como uma das possı́veis
soluções não exata deste problema. O trabalho faz uma introdução conceitual,
revisão dos trabalhos relacionados e apresenta o resultado dos experimentos
realizados.
1. Introdução
O interesse matemático por melhores soluções em grafos não é novidade, o teorema
de Turãan apresentado em seu trabalho em 1941 [Turaan 1941], por exemplo, faz uma
relação mı́nima para verificação grafos sem triângulos. A Teoria dos Grafos Extremais,
lida com problemas ligados a invariantes de grafos como grau máximo ou mı́nimo, clique,
número cromático, corte entre outros [Bollobas 1978].
Neste trabalho trataremos do problema do corte maximal ou corte máximo (Max-
Cut) de um grafo. O corte de um grafo é um conjunto de arestas que resulta ao final o
aumento do número de componentes conexas [Goldbarg 2012], mais a frente formaliza-
remos melhor. O Max-Cut se trata do conjunto de arestas com maior valor absoluto para
um determinado grafo. Devido a sua aplicabilidade em muitas áreas como segmentação
de imagens, fı́sica estatı́stica, circuitos integrados, circuitos intregrados de escala muito
grade (Very Large Scale Integrated (VLSI) Circuits)[Araujo 2018], entre outras, o estudo
deste problema de otimização é pertinente.
Foi introduzido por Stephen Cook, em 1971, o conceito de problemas de de-
cisão NP-completos e a partir deste resultado Richard Karp provou que 21 proble-
mas combinatórios são NP-completos através de sucessivas reduções do problema de
satisfabilidade Booleana, entre esses problemas o Problema do Corte Máximo é um
deles[Sucupira 2017].
Como o tempo de execução do problema do corte aumenta quanto maior o número
de vértices do grafo, existe um desafio na resolução ótima em grafos moderados, isto é,
com mais de 200 vértices [Araujo 2018]. Sendo assim o uso de força bruta se torna pouco
interessante em grafos mais robustos, portanto, o uso de soluções computacionais não
exatas, como heurı́sticas ou meta-heurı́sticas, ou estratégias matemáticas com base em
propriedades espectrais dos grafos se tornam mais plausı́veis.
Pretende-se nesse trabalho implementar a meta-heurı́stica Variable Neighborhood
Search (VNS) ou busca em vinhança variável para exploração de possı́veis soluções do
problema do corte, em sua versão mais básica ela trabalha com 3 etapas principais (a)
perturbação, (b) Busca Local e (c) melhora ou não [Hansen and Mladenović 2005], o uso
da técnica apresentou bons resultados na literatura, inclusive para o problema do corte,
indicando assim uma boa escolha para verificação dos resultados.
As principais referências utilizadas são artigos com resoluções heurı́sticas
[Caporossi and Hansen 2000] [Festa et al. 2002a] e técnicas matemáticas, utilizando gra-
fos espectrais[Vinagre 2006][Mohades and Kahaei 2022]. O objetivo deste trabalho não
é trazer inovações ao respeito da solução do problema de corte. O problema de corte será
usado na comparação de resultados ao respeito de um algoritmo exato de força bruta e um
algoritmo aproximado usando VNS. Numa etapa posterior, aplicaremos a mesma abor-
dagem para obter grafos extremais para o invariante espectral conectividade algébrica
considerando classes particulares de grafos.
Diante do exposto, o trabalho propôs-se a criação de algoritmo de força bruta
para resolução do problema Max-Cut para um conjunto de grafos, assim como a
implementação de um método heurı́stico utilizando o VNS, afim de se comparar os re-
sultados obtidos com o algoritmo exato. Nos experimentos utilizados foram utilizadas
instâncias reais do problema do corte em grafos pequenos (ref The House of Graphs) ,
tratadas na literatura, para testes comparativos da qualidade da implementação.
Na próxima seção faremos um aprofundamento dos conceitos básicos necessários
para o entendimento do trabalho, já na Seção 3 são indicados os trabalhos que já tra-
taram do tema deste artigo. Na Seção 4 será apresentada a abordagem utilizada. As
última seções são reservadas para apresentação dos experimentos e resultados, além das
considerações finais.
2. CONCEITOS BÁSICOS
2.1. O Problema do Corte Máximo (Max-Cut)
O corte de um grafo valorado G = (V,E), sem laços e restas múltiplas, onde V =
1, 2, ..., n é um conjunto de vértices de G e E = {{i, j} : i, j ∈ V } o conjunto de arestas,
é uma divisão de vértices em dois subconjuntos S e S, tal que, S ∩ S = ∅ e S ∪ S = V .
Podemos efetuar o calculo de um corte S em um grafo G com o seguinte calculo:
w(S, S) =
∑
{i,j}∈E(S,S)
aij (1)
O corte maximal de G, que denotaremos por mc(G) é definido pela função:
mc(G) = max
S⊂V
w(S, S) = max
S⊂V
∑
{i,j}∈E(S,S)
aij = max
S⊂V
∑
i∈S j∈V \S
aij (2)
Exemplos, sejam G1 e G2 os grafos com arestas de peso unitário (ai,j ≤ 1) re-
presentados nas figuras 1 e 2, os seus respectivos cortes maximais são mc(G1) = 6 e
mc(G2) = 3.
Figura 1. Grafo G1
Figura 2. Grafo G2
Uma possı́vel solução exata para o problema max-cut é a execução das 2n possibi-
lidades de cortes e comparar seus respectivos valores para encontrar seus valores de cortes
máximo, para n o número de vértices dos possı́veis grafos. A complexidade computaci-
onal necessária para estes cálculos é aproximadamente O(n2n) que é, para a maioria dos
casos, inviável [Mohades and Kahaei 2022].
Uma solução para o corte é o uso de algoritmos de ρ-aproximação, isto
é, ρ vezes distante da solução ótima do problema, uma 0.5-aproximação é apre-
sentada em 1976 [Sahni and Gonzalez 1976], uma 0.878-aproximação em 1995
[Goemans and Williamson 1995] e em 2022 foi sugerida uma 0.9597-aproximação
[Mohades and Kahaei 2022], embora o uso de tais algoritmos sejam bem satisfatórios
estes não apresentam resultado ótimo.
2.2. Variable Neighborhood Search (VNS)
Existem na literatura algumas meta-heurı́sticas já aplicadas para o problema do corte na
literatura, como o greedy randomized adaptive search procedure (procedimento de busca
adaptativa aleatória gulosa) GRASP, Scatter Search, VNS entre outras [Festa et al. 2002a]
[Martı́ et al. 2009] [Araujo 2018] [Chen et al. 2019].
O VNS é uma técnica meta-heurı́stica, proposta por Hansen e Mladenovi’c à mais
de 20 anos[Mladenović and Hansen 1997], ela é motivada pela busca sistemática em es-
truturas de vizinhança e fases de perturbação para saı́da de ótimos locais. A sua versa-
tilidade permitiu que a técnica pudesse ser utilizada em campos como a analise de clus-
ter, escalonamento, roteamento de veı́culos, filogenia, geometria, telecomunicação, etc
[Hansen et al. 2019].
A busca nas estruturas de vizinhança feita pelo VNS é incremental, a partir de uma
solução inicial x. Os três passos principais do VNS são os seguintes: geração da vinhança,
busca local e atualização ou não [Festa et al. 2002a]. O VNS inicia com uma solução
inicial e explora suas Nk vinhanças, K = 1, ..., kmax um conjunto total de estruturas e
Nk(x) uma possı́vel solução do conjunto, neste caso x é K-ésima solução de vizinhança
encontrada de uma determinada solução inicial. Na primeira fase, uma solução x′ ∈Nk(x) é escolhida, essa fase também é conhecida como fase de perturbação. Na segunda
fase do VNS uma busca local é executada e caso existam melhores soluções locais x′′ a
mesma é substituı́da em x′. Na última fase, é feito um teste de melhora de solução, caso
a mesma seja superior a inicial esta é substituı́da, isto é, x é trocado por x′′ caso contrário
a solução anterior é mantida. O processo das três fases é repetido até que um critério de
parada é atingido, seja ele quantidade de execuções ou limite de tempo. O pseudocódigo
do VNS pode ser visto no Algoritmo 1.
Algoritmo 1: VNS(maxIteracoes , kmax), retirado de [Festa et al. 2002a]
1 inı́cio
2 para cada i = 1,...,maxIteracoes faça
3 k ← 1;
4 Gerar solução inicial randômica x;
5 enquanto k ≤ kmax faça
6 Gerar solução randômica x′ ∈ N (k)(x);
7 x′′← BuscaLocal(x′);
8 se w(x′′) > w(x) então
9 x← x′′;
10 k← 1;
11 fim
12 senão
13 k← k + 1;
14 fim
15 fim
16 fim
17 fim
2.2.1. Variable Neighborhood Descent (VND)
A descida em vizinhança variável é uma heurı́stica que busca uma melhora local a partir
de uma solução x ∈ X em vizinhança N(x) passo a passo, até que todos os movimentos
possı́veis sejam explorados. A cada passo toda vizinhança de x é explorada completa-
mente, se em uma iteração x′ é melhor que x então um novo ótimo local é encontrado
e x ← x′ e uma nova iteração do VND vai se iniciar, a heurı́stica vai encerrar somente
quando toda vizinhança da solução testada for visitada e nenhuma melhora for encontrada.
O Algoritmo 2 descreve os passos do VND, esta heurı́stica foi usada como estratégia de
busca local do VNS para este trabalho.
Algoritmo 2: VND(x , kmax), retirado de [Hansen et al. 2019]
1 inı́cio
2 repita
3 x′← miny∈Nk(x)w(y);
4 x, k ←MudançaVizinhança (x,x′,k);
5 até k= kmax;
6 fim
3. TRABALHOS RELACIONADOS
Até onde foi verificado o problema do corte máximo é bem explorado na literatura e foram
encontrados alguns artigos utilizando meta-heurı́sticas com estratégias de busca local até
estratégias com uso de algoritmos genético e populacionais.
3.1. [Festa et al. 2002a] GRASP VNS Hı́brido
Nesse trabalho foram utilizadas as meta-heurı́sticas GRASP, VNS e uma versão hı́brida
do GRASP com VNS, em que o VNS é utilizado na etapa de busca local do GRASP, no
resultado final o VNS puro obteve os melhores resultados da pesquisa.
3.2. [Festa et al. 2002b] GRASP VNS PR
Nesse trabalho, dos mesmos autores do trabalho anterior, a estratégia path-relinking (re-
conexão de caminho (PR)) foi aplicada as metaheurı́sticas anteriores e foi percebido que
a mesma teve melhor aproveitamento com o GRASP, tornando-se assim a melhor escolha
em termos de tempo mas o VNS continua sendo a melhor técnica em termos de qualidade,
porém com longo tempo de execução.
3.3. [Montemayor et al. 2005] VNS GPU
O artigo trabalha com grafos esparsos e faz um mapeamento da matriz de adjacência na
GPU a fim de fazer um comparativo de eficiência com a CPU na resolução do problema
do corte.
3.4. [Martı́ et al. 2009] Scatter Search
É proposta uma heurı́stica baseada na meta-heurı́stica scatter search, esse trabalho faz um
comparativo com o VNSPR e com a heurı́stica CirCut, os resultados obtidos demostra-
ram que a heurı́stica obteve um número maior de melhores resultados conhecidos que as
outras.
3.5. [Wu et al. 2015] Tabu Search
A proposta desse trabalho é criar heurı́stica busca tabu hı́brida evolucionária e comparar
a mesma com outras heurı́sticas da literatura como Breakout Local Search (BLS), Global
Equilibrium Search (GES) e uma programação binária baseada no Path Relinking (PR2).
Os resultados obtidos neste trabalho foram melhores que os obtidos em 15 instâncias
apresentadas na literatura.
3.6. [Kim et al. 2019] HA/GA
Faz um estudo comparativo entre as meta-heurı́sticas busca harmônica e algoritmo
genético para o problema do corte máximo. Utilizou-se GA de estado geracional e de
estado estacionário, o melhor resultado encontrado foi com a busca harmônica.
3.7. [Chen et al. 2019] HBABC
Nesse trabalho é proposta uma estratégia meta-heurı́stica populacional hı́brida de colônia
de abelhas artificiais (Hybrid Binary Artifitial Bee Colony Algorithm - HBABC). Os re-
sultados foram comparados com as heurı́sticas Colônia de Formigas e Meta-heurı́stica
Hierárquica Social, a HBABC apresentou os melhores resultados para as instâncias utili-
zadas.
3.8. [Mohades and Kahaei 2022] Riemannian Gradient
Diferente dos trabalhos anteriores, este último utilizou um método de aproximação e não
um método meta-heurı́stico para resolução do problema do corte, porém seus resultados
obtidos correspondem a um avanço significativo na resolução dessa classe de problemas.
4. ABORDAGEM PROPOSTA
Esta seção está a metodologia utilizada no desenvolvimento do trabalho, assim como as
tecnologias, instâncias e as configurações da máquina utilizada para os experimentos.
4.1. Metodologia de Desenvolvimento
Devido a limitação de tempo do projeto, a abordagem inicial escolhida, foi a utilização
de instâncias retiradas do site The House of Graphs(www.hog.grinvin.org), fo-
ram selecionadas 9 instâncias aleatoriamente, no formato txt de matrizes de ad-
jacências, chamaremos estas instâncias de graph 26973, graph 16993, graph 47093,
graph graph2423, graph 8394, graph 10896, graph 14914, graph 15326 e
graph 3343. Posteriormente, foram feitos alguns testes com instâncias reais
(https://www.cise.ufl.edu/research/sparse/matrices/Gset/) para verificar a qualidade
da implementação.
Inicialmente foi desenvolvido um algoritmo recursivo de força bruta para teste de
todas as possibilidades possı́veis de corte de uma grafo G. O número de instâncias utili-
zadas foi reduzida pois verificou-se que o tempo de execução para os testes aumentavam
significativamente ao acrescentar um único vértice.
O método do VNS utilizou uma estrutura de conjuntos auxiliar para comparação
no deslocamento dos nós entre os conjuntos de S e S, ela também foi utilizada como o
kmax, isto é, limitou superiormente o máximo de iterações até que uma solução fosse
dada. Utilizou-se uma estrutura de dados Nodo para armazenar um nó e sua lista de
adjacência, mas o desempenho foi superior ao utilizar uma matriz global que fornecesse
o acesso direto para execução das operações. Foram feitas 5 execuções do VNS para cada
instância.
Percebeu-se que um dos métodos mais custosos é o de custo associado ao corte,
desta forma a utilização cautelosa deste cálculo é importante.
5. EXPERIMENTOS E RESULTADOS
Utilizou-se para a realização dos testes o ambiente de desenvolvimento windows 10
Home, intel i5-3230M CPU 2.60GHz, memória 6,00 GB, IDE Eclipse versão 4.24.0,
linguagem de programação Java 8. Os tempos apresentados nos experimentos foram me-
didos em segundos.
Os tamanhos dos grafos utilizados seguem na Tabela 1. Devido a limitação de
tempo, que veremos mais adiante, a instância com maior número de vértices que foi
analisada possui 34 vértices.
Instância ∥V ∥ ∥E∥
graph 26973 25 24
graph 16993 26 90
graph 47093 27 75
graph 2423 28 104
graph 8394 29 77
graph 10896 30 86
graph 14914 31 95
graph 15326 32 104
graph 3343 34 51
Tabela 1. Tamanho das Instâncias do The House of Graphs
Os experimentos foram executados primeiramente utilizando o métodos por força
bruta, pois a seu funcionamento exige uma busca por todo o espaço de soluções possı́veis
para uma determinada instância de Grafo, por tanto, representou o limite superior na es-
colha do tipo de grafo escolhido. Percebeu-se que o tempo necessário para percorrer
todas as soluções possı́veis de um grafo cresce na ordem de O(2|V |), e a melhor pode
ser encontrada durante os primeiros minutos de execução ou apenas próximo ao fim do
perı́odo. A meta-heurı́stica VNS obteve todos os melhores resultados de corte maximal
em tempo inferior a 1 segundo, para 5 execuções consecutivas do programa. Isso demons-
traque a estratégia utilizada pela busca local está correta e possui potencial para testes
mais robustos.
Para análise do desempenho da solução foi executado o VNS para as instâncias
G8, G9, G10 e G11 [Helmberg and Rendl 2000], a Tabela 3 mostra o tamanho dos grafos
utilizados e os resultados obtidos foram comparados com os melhores da literatura.
Na Tabela 4 podemos ver que existe uma diferença de até 16,67% entre as
instâncias testadas, isso indica que exite margem apara melhora na qualidade da estratégia
utilizada ou no número de testes aplicados que, comparado com os executados em outros
trabalhos foram poucos.
Instância Força Bruta (FB) VNS Diferença(FB - VNS)(%)Tempo Max-Cut Tempo Max-Cut
graph 26973 13,967 44 0,041 44 99,70645%
graph 16993 31,678 68 0,052 68 99,83585%
graph 47093 62,452 50 0,062 50 99,90072%
graph 2423 131,387 80 0,094 80 99,92846%
graph 8394 277,316 59 0,066 59 99,97620%
graph 10896 582,655 66 0,061 66 99,98953%
graph 14914 1235,829 73 0,085 73 99,99312%
graph 15326 2565,598 80 0,081 80 99,99684%
graph 3343 10450,816 44 0,068 44 99,99935%
Tabela 2. Comparativo força bruta e VNS
Instância ∥V ∥ ∥E∥
G8 800 19176
G9 800 19176
G10 800 19176
G11 800 1600
Tabela 3. Tamanho das Instâncias da Literatura
Instância Melhor Corte Conhecido Resultado do Obtido Diferença (%)
G8 2005 1898 5,34%
G9 2054 1929 6,09%
G10 2000 1882 5,90%
G11 564 470 16,67%
Tabela 4. Comparativo entre melhores resultados conhecidos e os obtidos no
trabalho
6. CONSIDERAÇÕES FINAIS
Neste trabalho foi apresentada a utilização da técnica VNS para resolução do problema
extremal do corte em grafos. Nosso objetivo foi fazer uma apresentação do problema, da
técnica VNS e VND, fazer um apanhado bibliográfico e apresenta a proposta executada.
Foi construı́do para o trabalho um programa de força bruta e um de VNS com
busca local VND para resolução do problema do corte maximal. Os resultados apresenta-
dos para as instâncias mais simples indicaram que a solução proposta obteve os melhores
resultados e que é uma solução válida. Em comparação com os melhores resultados da
literatura verificou-se que a ainda existe uma margem para melhora dos resultados.
Pretende-se trabalhar, como trabalho futuro, no problema da otimização da conec-
tividade algébrica em uma famı́lia especı́fica, os grafos outerplanares maximais utilizando
o VNS.
Referências
Araujo, C. V. D. (2018). Utilização de desigualdades válidas baseadas em condições de
otimalidade na construção de algoritmos heurı́sticos para o problema do corte máximo.
Monografia (Bacharel em Ciências da Computação), UFCE (Universidade Federal do
Ceará), Russa, Brasil.
Bollobas, B. (1978). Extremal Graph Theory, volume 11 of London Mathematical Soci-
ety. Academic Press, London.
Caporossi, G. and Hansen, P. (2000). Variable neighborhood search for extremal graphs:
1 the autographix system. Discrete Mathematics, 212(1):29–44.
Chen, X., Lin, G., and Xu, M. (2019). Applying a binary artificial bee colony algorithm
to the max-cut problem. In 2019 12th International Congress on Image and Signal
Processing, BioMedical Engineering and Informatics (CISP-BMEI), pages 1–4.
Festa, P., Pardalos, P., Resende, M., and Ribeiro, C. (2002a). Randomized heuristics for
the max-cut problem. Optimization Methods and Software, 17(6):1033–1058.
Festa, P., Pardalos, P. M., Resende, M. G. C., and Ribeiro, C. C. (2002b). Grasp and vns
for max-cut.
Goemans, M. X. and Williamson, D. P. (1995). Improved approximation algorithms for
maximum cut and satisfiability problems using semidefinite programming. J. ACM,
42(6):1115–1145.
Goldbarg, M. (2012). Grafos : conceitos, algoritmos e aplicações. Grupo GEN.
Hansen, P. and Mladenović, N. (2005). Variable Neighborhood Search, pages 211–238.
Springer US, Boston, MA.
Hansen, P., Mladenović, N., Brimberg, J., and Pérez, J. A. M. (2019). Variable Neigh-
borhood Search, pages 57–97. Springer International Publishing, Cham.
Helmberg, C. and Rendl, F. (2000). A spectral bundle method for semidefinite program-
ming. SIAM J. Optim., 10:673–696.
Kim, Y.-H., Yoon, Y., and Geem, Z. W. (2019). A comparison study of harmony search
and genetic algorithm for the max-cut problem. Swarm and Evolutionary Computation,
44:130–135.
Martı́, R., Duarte, A., and Laguna, M. (2009). Advanced scatter search for the max-cut
problem. INFORMS Journal on Computing, 21(1):26–38.
Mladenović, N. and Hansen, P. (1997). Variable neighborhood search. Computers Ope-
rations Research, 24(11):1097–1100.
Mohades, M. M. and Kahaei, M. H. (2022). An efficient riemannian gradient based algo-
rithm for max-cut problems. IEEE Transactions on Circuits and Systems II: Express
Briefs, 69(3):1882–1886.
Montemayor, A. S., Duarte, A., Pantrigo, J. J., and Cabido, R. (2005). High-performance
vns for the max-cut problem using commodity graphics hardware.
Sahni, S. and Gonzalez, T. (1976). P-complete approximation problems. J. ACM,
23(3):555–565.
Sucupira, R. A. (2017). PROBLEMAS DE CORTES DE ARESTAS MÁXIMOS E
MÍNIMOS EM GRAFOS. PhD thesis, UFRJ.
Turaan, P. (1941). Eine extremalaufgabe aus der graphentheorie. Mat. Fiz. Lapok, 48:436–
452.
Vinagre, C. T. M. (2006). Xxxviii simpósio brasileiro de pesquisa operacional. Minicurso.
Wu, Q., Wang, Y., and Lü, Z. (2015). A tabu search based hybrid evolutionary algorithm
for the max-cut problem. Applied Soft Computing, 34:827–837.

Outros materiais