{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T04:10:48Z","timestamp":1751429448819,"version":"3.41.0"},"reference-count":0,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2017,3,3]],"date-time":"2017-03-03T00:00:00Z","timestamp":1488499200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2017,3,3]]},"abstract":"<jats:p> The process of merging two arbitrary partitions of a given finite set \ud835\udcb0 of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions \ud835\udcb3, \ud835\udcb4 of the set \ud835\udcb0 such that \ud835\udcb3 = {\ud835\udcb3<jats:sub>1<\/jats:sub>, \ud835\udcb3<jats:sub>2<\/jats:sub>, ..., \ud835\udcb3<jats:sub> x<\/jats:sub>} and \ud835\udcb4 = {\ud835\udcb4<jats:sub>1<\/jats:sub>, \ud835\udcb4<jats:sub>2<\/jats:sub>, ..., \ud835\udcb4<jats:sub> y<\/jats:sub>}, and determine a new partition \ud835\udcb5 = {\ud835\udcb5<jats:sub>1<\/jats:sub>, \ud835\udcb5<jats:sub>2<\/jats:sub>, ..., \ud835\udcb5<jats:sub> z<\/jats:sub>} such that each is a common non-empty subset of some \ud835\udcb3<jats:sub> a<\/jats:sub> \u2208 \ud835\udcb3 and some \ud835\udcb4<jats:sub> b<\/jats:sub> \u2208 \ud835\udcb4 and |\ud835\udcb5| is as small as possible. This article describes a resource-efficient parallel algorithm to solve this problem. More specifically, we show that a coarsest refinement can be computed in O( t( n) + log n) parallel time using <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" overflow=\"scroll\" altimg=\"eq-00001.gif\"><mml:mrow><mml:mi>max<\/mml:mi><mml:mrow><mml:mo>{<\/mml:mo><mml:mrow><mml:mfrac><mml:mi>n<\/mml:mi><mml:mrow><mml:mi>log<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:mrow><\/mml:mfrac><mml:mo>,<\/mml:mo><mml:mi>p<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:mrow><mml:mo>}<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math> processors, where t( n) denotes the running time of a parallel stable sorting algorithm that uses p( n) processors on an EREW PRAM. This result depends on t( n) and p( n). We give a table that shows the best known time and processor complexities for a parallel stable sorting algorithm. If the parallel stable sorting algorithms by Ajtai et al., Cole, and Leighton are used, the coarsest refinement can be computed in O(log n) parallel time using n processors on an EREW PRAM. On the other hand, if the parallel stable sorting algorithm by Bahig et al. is used, the coarsest refinement can be computed in <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" overflow=\"scroll\" altimg=\"eq-00002.gif\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mrow><mml:mo>(<\/mml:mo><mml:mrow><mml:mi>log<\/mml:mi><mml:mi>n<\/mml:mi><mml:mi>log<\/mml:mi><mml:mrow><mml:mo>(<\/mml:mo><mml:mrow><mml:mfrac><mml:mi>n<\/mml:mi><mml:mrow><mml:mi>log<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:mrow><\/mml:mfrac><\/mml:mrow><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math> parallel time using <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" overflow=\"scroll\" altimg=\"eq-00003.gif\"><mml:mrow><mml:mfrac><mml:mi>n<\/mml:mi><mml:mrow><mml:mi>log<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:mrow><\/mml:mfrac><\/mml:mrow><\/mml:math> processors on an EREW PRAM. In addition, we show that on, a RAM machine, our parallel algorithm runs as asymptotically efficient as the fastest known sequential algorithm. <\/jats:p>","DOI":"10.3233\/fi-2017-1465","type":"journal-article","created":{"date-parts":[[2017,3,6]],"date-time":"2017-03-06T12:14:55Z","timestamp":1488802495000},"page":"211-220","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast and Efficient Parallel Coarsest Refinement"],"prefix":"10.1177","volume":"150","author":[{"given":"Nopadon","family":"Juneam","sequence":"first","affiliation":[{"name":"Department of Computer Science, Faculty of Science, Chiang Mai University, Chiang Mai, 50200, Thailand."}]},{"given":"Sanpawat","family":"Kantabutra","sequence":"additional","affiliation":[{"name":"The Theory of Computation Group, Department of Computer Engineering, Faculty of Engineering, Chiang Mai University, Chiang Mai, 50200, Thailand."}]}],"member":"179","published-online":{"date-parts":[[2017,3,3]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2017-1465","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2017-1465","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:50:00Z","timestamp":1751367000000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2017-1465"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,3]]},"references-count":0,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,3,3]]}},"alternative-id":["10.3233\/FI-2017-1465"],"URL":"https:\/\/doi.org\/10.3233\/fi-2017-1465","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"type":"print","value":"0169-2968"},{"type":"electronic","value":"1875-8681"}],"subject":[],"published":{"date-parts":[[2017,3,3]]}}}