File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: EFFICIENT PARALLEL ALGORITHMS FOR SOME GRAPH PROBLEMS.

TitleEFFICIENT PARALLEL ALGORITHMS FOR SOME GRAPH PROBLEMS.
Authors
Chin, Francis YLam, JohnINgo Chen
Keywordscomplexity
graph problems
optimal algorithms
parallel algorithms
SIMD
Issue Date1982
PublisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/cacm/
Citation
Communications Of The Acm, 1982, v. 25 n. 9, p. 659-665 How to Cite?
DOI: http://dx.doi.org/10.1145/358628.358650
AbstractParallel algorithms for a number of graph problems are studied, using the Single Instruction Stream-Multiple Data Stream model. It is assumed the processors have access to a common memory and that no memory or data alignment time penalties are incurred. A general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph is derived. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.
Persistent Identifierhttp://hdl.handle.net/10722/152211
ISSN
0001-0782
2021 Impact Factor: 14.065
2020 SCImago Journal Rankings: 0.967
ISI Accession Number ID
WOS:A1982PH13400010

 

DC FieldValueLanguage
dc.contributor.authorChin, Francis Yen_US
dc.contributor.authorLam, Johnen_US
dc.contributor.authorINgo Chenen_US
dc.date.accessioned2012-06-26T06:36:33Z-
dc.date.available2012-06-26T06:36:33Z-
dc.date.issued1982en_US
dc.identifier.citationCommunications Of The Acm, 1982, v. 25 n. 9, p. 659-665en_US
dc.identifier.issn0001-0782en_US
dc.identifier.urihttp://hdl.handle.net/10722/152211-
dc.description.abstractParallel algorithms for a number of graph problems are studied, using the Single Instruction Stream-Multiple Data Stream model. It is assumed the processors have access to a common memory and that no memory or data alignment time penalties are incurred. A general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph is derived. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.en_US
dc.languageengen_US
dc.publisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/cacm/en_US
dc.relation.ispartofCommunications of the ACMen_US
dc.subjectcomplexity-
dc.subjectgraph problems-
dc.subjectoptimal algorithms-
dc.subjectparallel algorithms-
dc.subjectSIMD-
dc.titleEFFICIENT PARALLEL ALGORITHMS FOR SOME GRAPH PROBLEMS.en_US
dc.typeArticleen_US
dc.identifier.emailChin, Francis Y:chin@cs.hku.hken_US
dc.identifier.authorityChin, Francis Y=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1145/358628.358650en_US
dc.identifier.scopuseid_2-s2.0-0020183349en_US
dc.identifier.volume25en_US
dc.identifier.issue9en_US
dc.identifier.spage659en_US
dc.identifier.epage665en_US
dc.identifier.isiWOS:A1982PH13400010-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChin, Francis Y=7005101915en_US
dc.identifier.scopusauthoridLam, John=7201973323en_US
dc.identifier.scopusauthoridINgo Chen=7409541843en_US
dc.identifier.issnl0001-0782-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats