File Download
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: On the parallel time complexity of undirected connectivity and minimum spanning trees
Title | On the parallel time complexity of undirected connectivity and minimum spanning trees |
---|---|
Authors | |
Keywords | Mathematics computers |
Issue Date | 1999 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | The Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), Baltimore, MD, 17-19 January 1999. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 225-234 How to Cite? |
Abstract | We present a new approach to finding minimum spanning trees of weighted undirected graphs on the parallel random access machine (PRAM) without concurrent-write power. This approach gives an algorithm that runs in O(log n) time using n+m processors on the EREW PRAM, settling a long-standing open problem in the literature. |
Persistent Identifier | http://hdl.handle.net/10722/45607 |
ISSN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chong, Ka Wong | en_HK |
dc.contributor.author | Han, Yijie | en_HK |
dc.contributor.author | Lam, Tak Wah | en_HK |
dc.date.accessioned | 2007-10-30T06:30:10Z | - |
dc.date.available | 2007-10-30T06:30:10Z | - |
dc.date.issued | 1999 | en_HK |
dc.identifier.citation | The Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), Baltimore, MD, 17-19 January 1999. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 225-234 | en_HK |
dc.identifier.issn | 1071-9040 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/45607 | - |
dc.description.abstract | We present a new approach to finding minimum spanning trees of weighted undirected graphs on the parallel random access machine (PRAM) without concurrent-write power. This approach gives an algorithm that runs in O(log n) time using n+m processors on the EREW PRAM, settling a long-standing open problem in the literature. | en_HK |
dc.format.extent | 1184500 bytes | - |
dc.format.extent | 1852 bytes | - |
dc.format.extent | 4181 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | text/plain | - |
dc.format.mimetype | text/plain | - |
dc.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. | en_HK |
dc.relation.ispartof | Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms | en_HK |
dc.rights | © 1999 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms in 1999, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Mathematics computers | en_HK |
dc.title | On the parallel time complexity of undirected connectivity and minimum spanning trees | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Lam, Tak Wah:twlam@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, Tak Wah=rp00135 | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.scopus | eid_2-s2.0-0032762081 | en_HK |
dc.identifier.hkuros | 40756 | - |
dc.identifier.spage | 225 | en_HK |
dc.identifier.epage | 234 | en_HK |
dc.identifier.scopusauthorid | Chong, Ka Wong=7102553941 | en_HK |
dc.identifier.scopusauthorid | Han, Yijie=7404096703 | en_HK |
dc.identifier.scopusauthorid | Lam, Tak Wah=7202523165 | en_HK |
dc.identifier.issnl | 1071-9040 | - |