A parallel approach to solving the MWPSP
Abstract
Algorithms for the problem of identifying a maximum edge-weight planar subgraph of a given edge-weighted graph G are relevant in a wide variety of application areas. In this paper, we propose a new local search constructive heuristic algorithm for this NP-hard problem that is based on existing methods for the problem and uses a parallel approach on GPU.
References
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.
Published
2022-10-25
How to Cite
CASTRO, Rafael S.; LONGO, Humberto J.; MARTINS, Wellington S..
A parallel approach to solving the MWPSP. In: REGIONAL SCHOOL ON INFORMATICS OF 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.
