Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Article type: Research Article
Authors: Juneam, Nopadona; โก; * | Kantabutra, Sanpawatb; *; โ
Affiliations: [a] Department of Computer Science, Faculty of Science, Chiang Mai University, Chiang Mai, 50200, Thailand. nopadon_j@cmu.ac.th | [b] The Theory of Computation Group, Department of Computer Engineering, Faculty of Engineering, Chiang Mai University, Chiang Mai, 50200, Thailand. sanpawat@alumni.tufts.edu
Correspondence: [โ ] Address for correspondence: The Theory of Computation Group, Department of Computer Engineering, Faculty of Engineering, Chiang Mai University, Chiang Mai, 50200, Thailand.
Note: [*] Financial support from the Thailand Research Fund through the Royal Golden Jubilee Ph.D. Program (Grant No. PHD/0267/2552) to studentโs initial NJ, advisorโs initial SK, and co-advisorโs initial RG is acknowledged.
Note: [โก] Also affiliated at: The Theory of Computation Group, Department of Computer Engineering Chiang Mai University.
Abstract: The process of merging two arbitrary partitions of a given finite set ๐ฐ of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions ๐ณ, ๐ด of the set ๐ฐ such that ๐ณ = {๐ณ1, ๐ณ2, ..., ๐ณx} and ๐ด = {๐ด1, ๐ด2, ..., ๐ดy}, and determine a new partition ๐ต = {๐ต1, ๐ต2, ..., ๐ตz} such that each is a common non-empty subset of some ๐ณa โ ๐ณ and some ๐ดb โ ๐ด and |๐ต| 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 max{nlogn,p(n)} 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 O(lognlog(nlogn)) parallel time using nlogn 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.
Keywords: PRAM algorithms, parallel computation, coarsest refinement, partition refinement
DOI: 10.3233/FI-2017-1465
Journal: Fundamenta Informaticae, vol. 150, no. 2, pp. 211-220, 2017
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
ๅฆๆๆจๅจๅบ็ๆน้ข้่ฆๅธฎๅฉๆๆไปปไฝๅปบ, ไปถ่ณ: editorial@iospress.nl