File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Improving the efficiency of parallel minimum spanning tree algorithms

TitleImproving the efficiency of parallel minimum spanning tree algorithms
Authors
Chong, KWHan, YIgarashi, YLam, TW
KeywordsConnected components
Graph algorithms
Minimum spanning trees
Parallel algorithms
PRAM
Issue Date2003
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/dam
Citation
Discrete Applied Mathematics, 2003, v. 126 n. 1, p. 33-54 How to Cite?
DOI: http://dx.doi.org/10.1016/S0166-218X(02)00560-7
AbstractThis paper presents results which improve the efficiency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(log n) time with O((m+n)√log n) operations. Our CRCW PRAM algorithm runs in O(log n) time with O((m+n)log log n) operations. We also show that for dense graphs we can achieve O(log n) time with O(n2) operations on the EREW PRAM. © 2002 Published by Elsevier Science B.V.
Persistent Identifierhttp://hdl.handle.net/10722/88917
ISSN
0166-218X
2023 Impact Factor: 1.0
2023 SCImago Journal Rankings: 0.657
ISI Accession Number ID
WOS:000180319000004

 

DC FieldValueLanguage
dc.contributor.authorChong, KWen_HK
dc.contributor.authorHan, Yen_HK
dc.contributor.authorIgarashi, Yen_HK
dc.contributor.authorLam, TWen_HK
dc.date.accessioned2010-09-06T09:50:06Z-
dc.date.available2010-09-06T09:50:06Z-
dc.date.issued2003en_HK
dc.identifier.citationDiscrete Applied Mathematics, 2003, v. 126 n. 1, p. 33-54en_HK
dc.identifier.issn0166-218Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/88917-
dc.description.abstractThis paper presents results which improve the efficiency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(log n) time with O((m+n)√log n) operations. Our CRCW PRAM algorithm runs in O(log n) time with O((m+n)log log n) operations. We also show that for dense graphs we can achieve O(log n) time with O(n2) operations on the EREW PRAM. © 2002 Published by Elsevier Science B.V.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/damen_HK
dc.relation.ispartofDiscrete Applied Mathematicsen_HK
dc.rightsDiscrete Applied Mathematics. Copyright © Elsevier BV.en_HK
dc.subjectConnected componentsen_HK
dc.subjectGraph algorithmsen_HK
dc.subjectMinimum spanning treesen_HK
dc.subjectParallel algorithmsen_HK
dc.subjectPRAMen_HK
dc.titleImproving the efficiency of parallel minimum spanning tree algorithmsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0166-218X&volume=126&issue=1&spage=33&epage=54&date=2003&atitle=Improving+the+efficiency+of+parallel+minimum+spanning+tree+algorithmsen_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.1016/S0166-218X(02)00560-7en_HK
dc.identifier.scopuseid_2-s2.0-84867960269en_HK
dc.identifier.hkuros91590en_HK
dc.identifier.volume126en_HK
dc.identifier.issue1en_HK
dc.identifier.spage33en_HK
dc.identifier.epage54en_HK
dc.identifier.isiWOS:000180319000004-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridChong, KW=7102553941en_HK
dc.identifier.scopusauthoridHan, Y=7404096703en_HK
dc.identifier.scopusauthoridIgarashi, Y=7401635175en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.issnl0166-218X-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats