File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Finding Connected Components in O(log n log log n) Time on the EREW PRAM

TitleFinding Connected Components in O(log n log log n) Time on the EREW PRAM
Authors
Issue Date1995
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor
Citation
Journal Of Algorithms, 1995, v. 18 n. 3, p. 378-402 How to Cite?
AbstractIn this paper, a parallel algorithm for finding the connected components of an undirected graph is presented. On a graph with n vertices and m edges, the algorithm runs in O(log n log log n) time using n + m processors on an EREW (exclusive-read and exclusive-write) PRAM. Prior to our work, the best exclusive-write algorithm known for this problem required O(log1.5n) time using n + m processors (D. B. Johnson and P. Metaxas, in "Proceedings 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 688-697; D. R. Karger, N. Nisan, and M. Parnas, in "Proceedings 4th Annual ACM Symposium on Parallel Architectures and Algorithms, 1992," pp. 373-381; N. Nisan, S. Szemerdi, and A. Wigderson, in "Proceedings 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992," pp. 24-29). © 1995 Academic Press. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152294
ISSN
2011 Impact Factor: 0.5
2012 SCImago Journal Rankings: 0.469
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChong, KWen_US
dc.contributor.authorLam, TWen_US
dc.date.accessioned2012-06-26T06:36:59Z-
dc.date.available2012-06-26T06:36:59Z-
dc.date.issued1995en_US
dc.identifier.citationJournal Of Algorithms, 1995, v. 18 n. 3, p. 378-402en_US
dc.identifier.issn0196-6774en_US
dc.identifier.urihttp://hdl.handle.net/10722/152294-
dc.description.abstractIn this paper, a parallel algorithm for finding the connected components of an undirected graph is presented. On a graph with n vertices and m edges, the algorithm runs in O(log n log log n) time using n + m processors on an EREW (exclusive-read and exclusive-write) PRAM. Prior to our work, the best exclusive-write algorithm known for this problem required O(log1.5n) time using n + m processors (D. B. Johnson and P. Metaxas, in "Proceedings 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 688-697; D. R. Karger, N. Nisan, and M. Parnas, in "Proceedings 4th Annual ACM Symposium on Parallel Architectures and Algorithms, 1992," pp. 373-381; N. Nisan, S. Szemerdi, and A. Wigderson, in "Proceedings 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992," pp. 24-29). © 1995 Academic Press. All rights reserved.en_US
dc.languageengen_US
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgoren_US
dc.relation.ispartofJournal of Algorithmsen_US
dc.titleFinding Connected Components in O(log n log log n) Time on the EREW PRAMen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1006/jagm.1995.1016en_US
dc.identifier.scopuseid_2-s2.0-0038474549en_US
dc.identifier.hkuros1262-
dc.identifier.volume18en_US
dc.identifier.issue3en_US
dc.identifier.spage378en_US
dc.identifier.epage402en_US
dc.identifier.isiWOS:A1995RB98400002-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChong, KW=7102553941en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats