Uma proposta de solução aproximada para o problema do subgrafo planar de peso máximo
Abstract
This work introduces approximate algorithms for the Weighted Maximal Planar Graph Problem (WMPG). The algorithms are based on a "dimpling" approach that successively inserts vertices, within faces of the graph. This method has the advantage that any graph generated by it is a maximal planar graph, thus obviating the need for graph planarity testing. We present both sequential and parallel dimpling algorithms for the WMPG and their implementations. Several tests were performed on instances with up to 85 vertices to evaluate both types of algorithms. Results obtained with the parallel versions, implemented on a manycore architecture, were up to 107 times faster than the sequential version.References
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.
Published
2016-10-05
How to Cite
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: SYMPOSIUM ON HIGH PERFORMANCE COMPUTING SYSTEMS (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.
