File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Finding connected components in O(log n loglog n) time on the EREW PRAM

TitleFinding connected components in O(log n loglog n) time on the EREW PRAM
Authors
Chong, Ka WongLam, Tak Wah
Issue Date1993
PublisherSociety for Industrial and Applied Mathematics.
Citation
Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, p. 11-20 How to Cite?
AbstractIn this paper we present a new parallel algorithm for finding the connected components of an undirected graph. On a graph with n vertices and m edges, the algorithm runs in O(log n loglog n) time using n+m processors on an EREW (exclusive-read and exclusive-write) PRAM. Prior to our work, the best known exclusive-write algorithm for this problem requires O(log1.5 n) time using n+m processors [JM91, KNP92].
Persistent Identifierhttp://hdl.handle.net/10722/151794

 

DC FieldValueLanguage
dc.contributor.authorChong, Ka Wongen_US
dc.contributor.authorLam, Tak Wahen_US
dc.date.accessioned2012-06-26T06:29:34Z-
dc.date.available2012-06-26T06:29:34Z-
dc.date.issued1993en_US
dc.identifier.citationProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, p. 11-20en_US
dc.identifier.urihttp://hdl.handle.net/10722/151794-
dc.description.abstractIn this paper we present a new parallel algorithm for finding the connected components of an undirected graph. On a graph with n vertices and m edges, the algorithm runs in O(log n loglog n) time using n+m processors on an EREW (exclusive-read and exclusive-write) PRAM. Prior to our work, the best known exclusive-write algorithm for this problem requires O(log1.5 n) time using n+m processors [JM91, KNP92].en_US
dc.languageengen_US
dc.publisherSociety for Industrial and Applied Mathematics.-
dc.relation.ispartofProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithmsen_US
dc.titleFinding connected components in O(log n loglog n) time on the EREW PRAMen_US
dc.typeConference_Paperen_US
dc.identifier.emailLam, Tak Wah:twlam@cs.hku.hken_US
dc.identifier.authorityLam, Tak Wah=rp00135en_US
dc.identifier.scopuseid_2-s2.0-0027146874en_US
dc.identifier.spage11en_US
dc.identifier.epage20en_US
dc.identifier.scopusauthoridChong, Ka Wong=7102553941en_US
dc.identifier.scopusauthoridLam, Tak Wah=7202523165en_US

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats