File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1006/jagm.1995.1016
- Scopus: eid_2-s2.0-0038474549
- WOS: WOS:A1995RB98400002
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Finding Connected Components in O(log n log log n) Time on the EREW PRAM
Title | Finding Connected Components in O(log n log log n) Time on the EREW PRAM |
---|---|
Authors | |
Issue Date | 1995 |
Publisher | Academic 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? |
Abstract | In 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 Identifier | http://hdl.handle.net/10722/152294 |
ISSN | 2011 Impact Factor: 0.500 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chong, KW | en_US |
dc.contributor.author | Lam, TW | en_US |
dc.date.accessioned | 2012-06-26T06:36:59Z | - |
dc.date.available | 2012-06-26T06:36:59Z | - |
dc.date.issued | 1995 | en_US |
dc.identifier.citation | Journal Of Algorithms, 1995, v. 18 n. 3, p. 378-402 | en_US |
dc.identifier.issn | 0196-6774 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/152294 | - |
dc.description.abstract | In 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.language | eng | en_US |
dc.publisher | Academic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor | en_US |
dc.relation.ispartof | Journal of Algorithms | en_US |
dc.title | Finding Connected Components in O(log n log log n) Time on the EREW PRAM | en_US |
dc.type | Article | en_US |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_US |
dc.identifier.authority | Lam, TW=rp00135 | en_US |
dc.description.nature | link_to_subscribed_fulltext | en_US |
dc.identifier.doi | 10.1006/jagm.1995.1016 | en_US |
dc.identifier.scopus | eid_2-s2.0-0038474549 | en_US |
dc.identifier.hkuros | 1262 | - |
dc.identifier.volume | 18 | en_US |
dc.identifier.issue | 3 | en_US |
dc.identifier.spage | 378 | en_US |
dc.identifier.epage | 402 | en_US |
dc.identifier.isi | WOS:A1995RB98400002 | - |
dc.publisher.place | United States | en_US |
dc.identifier.scopusauthorid | Chong, KW=7102553941 | en_US |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_US |
dc.identifier.issnl | 0196-6774 | - |