File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/0213036
- Scopus: eid_2-s2.0-0021474651
- WOS: WOS:A1984TB32600008
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Efficient parallel algorithms for a class of graph theoretic problems
| Title | Efficient parallel algorithms for a class of graph theoretic problems |
|---|---|
| Authors | |
| Issue Date | 1984 |
| Publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php |
| Citation | SIAM Journal On Computing, 1984, v. 13 n. 3, p. 580-599 How to Cite? |
| Abstract | The authors present efficient parallel algorithms for the following graph problems: finding the lowest common ancestors for vertex pairs of a directed tree; finding all fundamental cycles, a directed spanning forest, all bridges, all bridge-connected components, all separation vertices, all biconnected components, and testing the biconnectivity of an undirected graph. All these algorithms achieve the O(lg**2n) time bound. |
| Persistent Identifier | http://hdl.handle.net/10722/152217 |
| ISSN | 2023 Impact Factor: 1.2 2023 SCImago Journal Rankings: 2.143 |
| ISI Accession Number ID |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Tsin, Yung H | en_US |
| dc.contributor.author | Chin, Francis Y | en_US |
| dc.date.accessioned | 2012-06-26T06:36:35Z | - |
| dc.date.available | 2012-06-26T06:36:35Z | - |
| dc.date.issued | 1984 | en_US |
| dc.identifier.citation | SIAM Journal On Computing, 1984, v. 13 n. 3, p. 580-599 | en_US |
| dc.identifier.issn | 0097-5397 | en_US |
| dc.identifier.uri | http://hdl.handle.net/10722/152217 | - |
| dc.description.abstract | The authors present efficient parallel algorithms for the following graph problems: finding the lowest common ancestors for vertex pairs of a directed tree; finding all fundamental cycles, a directed spanning forest, all bridges, all bridge-connected components, all separation vertices, all biconnected components, and testing the biconnectivity of an undirected graph. All these algorithms achieve the O(lg**2n) time bound. | en_US |
| dc.language | eng | en_US |
| dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php | - |
| dc.relation.ispartof | SIAM Journal on Computing | en_US |
| dc.rights | © 1984 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 13, issue 3, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
| dc.title | Efficient parallel algorithms for a class of graph theoretic problems | en_US |
| dc.type | Article | en_US |
| dc.identifier.email | Chin, Francis Y:chin@cs.hku.hk | en_US |
| dc.identifier.authority | Chin, Francis Y=rp00105 | en_US |
| dc.description.nature | published_or_final_version | en_US |
| dc.identifier.doi | 10.1137/0213036 | - |
| dc.identifier.scopus | eid_2-s2.0-0021474651 | en_US |
| dc.identifier.volume | 13 | en_US |
| dc.identifier.issue | 3 | en_US |
| dc.identifier.spage | 580 | en_US |
| dc.identifier.epage | 599 | en_US |
| dc.identifier.isi | WOS:A1984TB32600008 | - |
| dc.publisher.place | United States | en_US |
| dc.identifier.scopusauthorid | Tsin, Yung H=6603741679 | en_US |
| dc.identifier.scopusauthorid | Chin, Francis Y=7005101915 | en_US |
| dc.identifier.issnl | 0097-5397 | - |