Uma proposta de solução aproximada para o problema do subgrafo planar de peso máximo
Resumo
A proposta deste trabalho consiste em uma solução aproximada para o problema do subgrafo planar de peso máximo (WMPG Weighted Maximal Planar Graph). O algoritmo baseia-se na adição de vértices, aproveitando-se da construção de triangulações nas faces do grafo. A vantagem do uso deste algoritmo dá-se pelo fato que todo grafo gerado por ele é maximal planar, descartando a necessidade de um teste de planaridade. Apresentamos um algoritmo sequencial e um paralelo para o problema WMPG e suas respectivas implementações. Os resultados obtidos com a versão paralela executando em uma arquitetura manycore, com instâncias de até 85 vértices, apresentaram speedups de até 107 vezes em relação à solução sequencial.Referências
Foulds, L. R. (1992). Graph Theory Applications. Springer, New York.
Foulds, L. R. and Robinson, D. F. (1976). A Strategy for Solving The Plant Layout Problem. Journal of the Operational Research Society, 27(4):845–855.
Foulds, L. R. and Robinson, D. F. (1978). Graph theoretic heuristics for the plant layout problem. International Journal of Production Research, 16(1):27–37.
Foulds, L. R. and Robinson, D. F. (1979). Construction Properties of Combinatorial Deltahedra. Discrete Applied Mathematics, 1:75–87.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York.
Kirk, D. B. and Hwu, W.-M. W. (2011). Programando Para Processadores Paralelos: Uma Abordagem Prática à Programação de GPU. Elsevier.
Massara, G. P., Di Matteo, T., and Aste, T. (2015). Network Filtering for Big Data: Triangulated Maximally Filtered Graph. CoRR, pages 1–18.
Tumminello, M., Aste, T., Di Matteo, T., and Mantegna, R. N. (2005). A tool for ltering information in complex systems. Proceedings of the National Academy of Sciences of the United States of America, 102(30):10421–10426.
Foulds, L. R. and Robinson, D. F. (1976). A Strategy for Solving The Plant Layout Problem. Journal of the Operational Research Society, 27(4):845–855.
Foulds, L. R. and Robinson, D. F. (1978). Graph theoretic heuristics for the plant layout problem. International Journal of Production Research, 16(1):27–37.
Foulds, L. R. and Robinson, D. F. (1979). Construction Properties of Combinatorial Deltahedra. Discrete Applied Mathematics, 1:75–87.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York.
Kirk, D. B. and Hwu, W.-M. W. (2011). Programando Para Processadores Paralelos: Uma Abordagem Prática à Programação de GPU. Elsevier.
Massara, G. P., Di Matteo, T., and Aste, T. (2015). Network Filtering for Big Data: Triangulated Maximally Filtered Graph. CoRR, pages 1–18.
Tumminello, M., Aste, T., Di Matteo, T., and Mantegna, R. N. (2005). A tool for ltering information in complex systems. Proceedings of the National Academy of Sciences of the United States of America, 102(30):10421–10426.
Publicado
05/10/2016
Como Citar
COELHO, Vinícius; MARTINS, Wellington; FOULDS, Leslie; DIAS, Elisângela; CASTONGUAY, Diane; LONGO, Humberto.
Uma proposta de solução aproximada para o problema do subgrafo planar de peso máximo. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 17. , 2016, Aracajú.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 49-60.
DOI: https://doi.org/10.5753/wscad.2016.14247.
