File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Concurrent threads and optimal parallel minimum spanning trees algorithm

TitleConcurrent threads and optimal parallel minimum spanning trees algorithm
Authors
KeywordsConnected components
EREW PRAM
Minimum spanning trees
Parallel algorithms
Issue Date2001
PublisherAssociation 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?
AbstractThis 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 Identifierhttp://hdl.handle.net/10722/89159
ISSN
2015 Impact Factor: 1.803
2015 SCImago Journal Rankings: 2.509
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChong, KAWen_HK
dc.contributor.authorHan, Yen_HK
dc.contributor.authorLam, TWen_HK
dc.date.accessioned2010-09-06T09:53:07Z-
dc.date.available2010-09-06T09:53:07Z-
dc.date.issued2001en_HK
dc.identifier.citationJournal Of The Acm, 2001, v. 48 n. 2, p. 297-323en_HK
dc.identifier.issn0004-5411en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89159-
dc.description.abstractThis 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.languageengen_HK
dc.publisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/jacmen_HK
dc.relation.ispartofJournal of the ACMen_HK
dc.rightsJournal of ACM. Copyright © Association for Computing Machinery.en_HK
dc.subjectConnected componentsen_HK
dc.subjectEREW PRAMen_HK
dc.subjectMinimum spanning treesen_HK
dc.subjectParallel algorithmsen_HK
dc.titleConcurrent threads and optimal parallel minimum spanning trees algorithmen_HK
dc.typeArticleen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/375827.375847en_HK
dc.identifier.scopuseid_2-s2.0-0000523923en_HK
dc.identifier.hkuros57738en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0000523923&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume48en_HK
dc.identifier.issue2en_HK
dc.identifier.spage297en_HK
dc.identifier.epage323en_HK
dc.identifier.isiWOS:000169174100006-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChong, KAW=7102553993en_HK
dc.identifier.scopusauthoridHan, Y=7404096703en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats