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
KeywordsMathematics computers
Issue Date1999
PublisherSociety for Industrial and Applied Mathematics.
Citation
Proceedings Of The 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

 

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.citationProceedings Of The 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 Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectMathematics computersen_HK
dc.titleOn the parallel time complexity of undirected connectivity and minimum spanning treesen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1071-9040&volume=&spage=225&epage=234&date=1999&atitle=On+the+parallel+time+complexity+of+undirected+connectivity+and+minimum+spanning+treesen_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

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats