File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Improved parallel algorithms for finding connected components

TitleImproved parallel algorithms for finding connected components
Authors
Chong, KWLam, TW
Issue Date1995
PublisherIEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000029
Citation
Ieee International Conference On Algorithms And Architectures For Parallel Processing, 1995, v. 1, p. 452-459 How to Cite?
DOI: http://dx.doi.org/10.1109/ICAPP.1995.472217
AbstractFinding the connected components of a graph is a basic computational problem. In recent years, there were several exciting results in breaking the log2 n-time barrier to finding connected components on parallel machines using shared memory without concurrent-write capability. This paper further presents two new parallel algorithms both using less than log2 n time. The merit of the first algorithm is that it uses only a sublinear number of processors, yet retains the time complexity of the fastest existing algorithm. The second algorithm is slightly slower but its work (i.e., the time-processor product) is closer to optimal than all previous algorithms using less than log2 n time.
Persistent Identifierhttp://hdl.handle.net/10722/45553

 

DC FieldValueLanguage
dc.contributor.authorChong, KWen_HK
dc.contributor.authorLam, TWen_HK
dc.date.accessioned2007-10-30T06:29:02Z-
dc.date.available2007-10-30T06:29:02Z-
dc.date.issued1995en_HK
dc.identifier.citationIeee International Conference On Algorithms And Architectures For Parallel Processing, 1995, v. 1, p. 452-459en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45553-
dc.description.abstractFinding the connected components of a graph is a basic computational problem. In recent years, there were several exciting results in breaking the log2 n-time barrier to finding connected components on parallel machines using shared memory without concurrent-write capability. This paper further presents two new parallel algorithms both using less than log2 n time. The merit of the first algorithm is that it uses only a sublinear number of processors, yet retains the time complexity of the fastest existing algorithm. The second algorithm is slightly slower but its work (i.e., the time-processor product) is closer to optimal than all previous algorithms using less than log2 n time.en_HK
dc.format.extent542046 bytes-
dc.format.extent4181 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherIEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000029en_HK
dc.relation.ispartofIEEE International Conference on Algorithms and Architectures for Parallel Processingen_HK
dc.rights©1995 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.-
dc.titleImproved parallel algorithms for finding connected componentsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/ICAPP.1995.472217en_HK
dc.identifier.scopuseid_2-s2.0-0029218393en_HK
dc.identifier.hkuros1265-
dc.identifier.volume1en_HK
dc.identifier.spage452en_HK
dc.identifier.epage459en_HK
dc.identifier.scopusauthoridChong, KW=7102553941en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats