Uma abordagem paralela para resolução do MWPSP
Resumo
O problema de se identificar em um grafo G, ponderado nas arestas, um subgrafo planar de peso máximo pertence à classe NP-difícil. Esse problema é importante na modelagem e resolução de problemas das mais diversas áreas. É proposto um novo algoritmo heurístico de busca local, baseado em métodos previamente existentes de construção, o qual usa paralelismo de GPU.
Referências
Alexander, J. W. (1930). The combinatorial theory of complexes. Ann Math, 31:292–320.
Coelho, V. S., Martins, W. S., Foulds, L. R., Dias, E. S., Castonguay, D., and Longo, H. J. (2016). Uma proposta de solução aproximada para o problema do subgrafo planar de peso máximo. In XVII Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD 2016), pages 16–27.
Foulds, L. R. and Robinson, D. F. (1978). Graph theoretic heuristics for the plant layout problem. Int J Prod Res, 16(1):27–37.
Leung, J. (1992). A New Graph-Theoretic Heuristic for Facility Layout. Manage Sci, 38(4):594–605.
Massara, G. P., Di Matteo, T., and Aste, T. (2017). Network filtering for big data: Triangulated maximally filtered graph. J Complex Netw, 5(2):1–18.
Merker, J. and Wäscher, G. (1997). Two new heuristic algorithms for the maximal planar layout problem. OR Spectr, 19(2):131–137.
Tumminello, M., Aste, T., Di Matteo, T., and Mantegna, R. N. (2005). A tool for filtering information in complex systems. Proc Natl Acad Sci, 102(30):10421–10426.
Coelho, V. S., Martins, W. S., Foulds, L. R., Dias, E. S., Castonguay, D., and Longo, H. J. (2016). Uma proposta de solução aproximada para o problema do subgrafo planar de peso máximo. In XVII Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD 2016), pages 16–27.
Foulds, L. R. and Robinson, D. F. (1978). Graph theoretic heuristics for the plant layout problem. Int J Prod Res, 16(1):27–37.
Leung, J. (1992). A New Graph-Theoretic Heuristic for Facility Layout. Manage Sci, 38(4):594–605.
Massara, G. P., Di Matteo, T., and Aste, T. (2017). Network filtering for big data: Triangulated maximally filtered graph. J Complex Netw, 5(2):1–18.
Merker, J. and Wäscher, G. (1997). Two new heuristic algorithms for the maximal planar layout problem. OR Spectr, 19(2):131–137.
Tumminello, M., Aste, T., Di Matteo, T., and Mantegna, R. N. (2005). A tool for filtering information in complex systems. Proc Natl Acad Sci, 102(30):10421–10426.
Publicado
25/10/2022
Como Citar
CASTRO, Rafael S.; LONGO, Humberto J.; MARTINS, Wellington S..
Uma abordagem paralela para resolução do MWPSP. In: ESCOLA REGIONAL DE INFORMÁTICA DE GOIÁS (ERI-GO), 10. , 2022, Goiás.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 181-184.
DOI: https://doi.org/10.5753/erigo.2022.227688.
