File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: On the parallel time complexity of undirected connectivity and minimum spanning trees

TitleOn the parallel time complexity of undirected connectivity and minimum spanning trees
Authors
Chong, Ka WongHan, YijieLam, Tak Wah
KeywordsMathematics computers
Issue Date1999
PublisherSociety 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?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/45607
ISSN
1071-9040

 

DC FieldValueLanguage
dc.contributor.authorChong, Ka Wongen_HK
dc.contributor.authorHan, Yijieen_HK
dc.contributor.authorLam, Tak Wahen_HK
dc.date.accessioned2007-10-30T06:30:10Z-
dc.date.available2007-10-30T06:30:10Z-
dc.date.issued1999en_HK
dc.identifier.citationThe 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-234en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45607-
dc.description.abstractWe 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.extent1184500 bytes-
dc.format.extent1852 bytes-
dc.format.extent4181 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofProceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithmsen_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.subjectMathematics computersen_HK
dc.titleOn the parallel time complexity of undirected connectivity and minimum spanning treesen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, Tak Wah:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, Tak Wah=rp00135en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.scopuseid_2-s2.0-0032762081en_HK
dc.identifier.hkuros40756-
dc.identifier.spage225en_HK
dc.identifier.epage234en_HK
dc.identifier.scopusauthoridChong, Ka Wong=7102553941en_HK
dc.identifier.scopusauthoridHan, Yijie=7404096703en_HK
dc.identifier.scopusauthoridLam, Tak Wah=7202523165en_HK
dc.identifier.issnl1071-9040-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats