{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:45:02Z","timestamp":1777675502349,"version":"3.51.4"},"reference-count":25,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2018,10,14]],"date-time":"2018-10-14T00:00:00Z","timestamp":1539475200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["Proc. FAPESP 2014\/50937-1"],"award-info":[{"award-number":["Proc. FAPESP 2014\/50937-1"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2019,5]]},"abstract":"<jats:p>Computing a spanning tree (ST) and a minimum ST (MST) of a graph are fundamental problems in graph theory and arise as a subproblem in many applications. In this article, we propose parallel algorithms to these problems. One of the steps of previous parallel MST algorithms relies on the heavy use of parallel list ranking which, though efficient in theory, is very time-consuming in practice. Using a different approach with a graph decomposition, we devised new parallel algorithms that do not make use of the list ranking procedure. We proved that our algorithms are correct, and for a graph [Formula: see text], [Formula: see text], and [Formula: see text], the algorithms can be executed on a Bulk Synchronous Parallel\/Coarse Grained Multicomputer (BSP\/CGM) model using [Formula: see text] communications rounds with [Formula: see text] computation time for each round. To show that our algorithms have good performance on real parallel machines, we have implemented them on graphics processing unit. The obtained speedups are competitive and showed that the BSP\/CGM model is suitable for designing general purpose parallel algorithms.<\/jats:p>","DOI":"10.1177\/1094342018803672","type":"journal-article","created":{"date-parts":[[2018,10,15]],"date-time":"2018-10-15T01:28:38Z","timestamp":1539566918000},"page":"444-461","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["New BSP\/CGM algorithms for spanning trees"],"prefix":"10.1177","volume":"33","author":[{"given":"Jucele Fran\u00e7a de Alencar","family":"Vasconcellos","sequence":"first","affiliation":[{"name":"College of Computing, Universidade Federal de Mato Grosso do Sul, Campo Grande, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edson Norberto","family":"C\u00e1ceres","sequence":"additional","affiliation":[{"name":"College of Computing, Universidade Federal de Mato Grosso do Sul, Campo Grande, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henrique","family":"Mongelli","sequence":"additional","affiliation":[{"name":"College of Computing, Universidade Federal de Mato Grosso do Sul, Campo Grande, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siang Wun","family":"Song","sequence":"additional","affiliation":[{"name":"Institute of Mathematics and Statistics, University of S\u00e3o Paulo, S\u00e3o Paulo, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Dehne","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayme Luiz","family":"Szwarcfiter","sequence":"additional","affiliation":[{"name":"NCE, COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2018,10,14]]},"reference":[{"key":"bibr1-1094342018803672","volume-title":"Technical Report RT-MAC-2003-06","author":"C\u00e1ceres EN","year":"2003"},{"key":"bibr2-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27866-5_110"},{"key":"bibr3-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626493000265"},{"key":"bibr4-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1109\/HPCS.2010.5547062"},{"key":"bibr5-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000241"},{"key":"bibr6-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0109-4"},{"key":"bibr7-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1985.10011"},{"key":"bibr8-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2010.07.002"},{"key":"bibr9-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1145\/359138.359141"},{"key":"bibr10-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1145\/107004.107032"},{"key":"bibr11-1094342018803672","volume-title":"Handbook of Theoretical Computer Science","author":"Karp RM","year":"1990"},{"key":"bibr12-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4400-4"},{"key":"bibr13-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"bibr14-1094342018803672","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13173-016-0041-8","volume":"22","author":"Lima ACD","year":"2016","journal-title":"Journal of The Brazilian Computer Society (Online)"},{"key":"bibr15-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1109\/ISCC.2016.7543874"},{"key":"bibr16-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1109\/HPCS.2017.100"},{"key":"bibr17-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.002"},{"key":"bibr18-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442531"},{"key":"bibr19-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145842"},{"key":"bibr20-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972894.5"},{"key":"bibr21-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"bibr22-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"bibr23-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"bibr24-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1109\/SBAC-PADW.2017.20"},{"key":"bibr25-1094342018803672","doi-asserted-by":"publisher","DOI":"10.1145\/1572769.1572796"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342018803672","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/1094342018803672","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342018803672","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:15:41Z","timestamp":1777450541000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342018803672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,14]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["10.1177\/1094342018803672"],"URL":"https:\/\/doi.org\/10.1177\/1094342018803672","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,14]]}}}