File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/375827.375847
- Scopus: eid_2-s2.0-0000523923
- WOS: WOS:000169174100006
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Concurrent threads and optimal parallel minimum spanning trees algorithm
Title | Concurrent threads and optimal parallel minimum spanning trees algorithm |
---|---|
Authors | |
Keywords | Connected components EREW PRAM Minimum spanning trees Parallel algorithms |
Issue Date | 2001 |
Publisher | Association for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/jacm |
Citation | Journal Of The Acm, 2001, v. 48 n. 2, p. 297-323 How to Cite? |
Abstract | This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in O(log n) time. Specifically, we present a new algorithm to solve these problems in O(log n) time using a linear number of processors on the exclusive-read exclusive-write PRAM. The logarithmic time bound is actually optimal since it is well known that even computing the "OR" of n bits requires Ω(log n) time on the exclusive-write PRAM. The efficiency achieved by the new algorithm is based on a new schedule which can exploit a high degree of parallelism. |
Persistent Identifier | http://hdl.handle.net/10722/89159 |
ISSN | 2023 Impact Factor: 2.3 2023 SCImago Journal Rankings: 2.866 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chong, KAW | en_HK |
dc.contributor.author | Han, Y | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.date.accessioned | 2010-09-06T09:53:07Z | - |
dc.date.available | 2010-09-06T09:53:07Z | - |
dc.date.issued | 2001 | en_HK |
dc.identifier.citation | Journal Of The Acm, 2001, v. 48 n. 2, p. 297-323 | en_HK |
dc.identifier.issn | 0004-5411 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89159 | - |
dc.description.abstract | This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in O(log n) time. Specifically, we present a new algorithm to solve these problems in O(log n) time using a linear number of processors on the exclusive-read exclusive-write PRAM. The logarithmic time bound is actually optimal since it is well known that even computing the "OR" of n bits requires Ω(log n) time on the exclusive-write PRAM. The efficiency achieved by the new algorithm is based on a new schedule which can exploit a high degree of parallelism. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Association for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/jacm | en_HK |
dc.relation.ispartof | Journal of the ACM | en_HK |
dc.rights | Journal of ACM. Copyright © Association for Computing Machinery. | en_HK |
dc.subject | Connected components | en_HK |
dc.subject | EREW PRAM | en_HK |
dc.subject | Minimum spanning trees | en_HK |
dc.subject | Parallel algorithms | en_HK |
dc.title | Concurrent threads and optimal parallel minimum spanning trees algorithm | en_HK |
dc.type | Article | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/375827.375847 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0000523923 | en_HK |
dc.identifier.hkuros | 57738 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0000523923&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 48 | en_HK |
dc.identifier.issue | 2 | en_HK |
dc.identifier.spage | 297 | en_HK |
dc.identifier.epage | 323 | en_HK |
dc.identifier.isi | WOS:000169174100006 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Chong, KAW=7102553993 | en_HK |
dc.identifier.scopusauthorid | Han, Y=7404096703 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.issnl | 0004-5411 | - |