A new graph triconnectivity algorithm and its parallelization
| Author(s) : | Vijaya Ramachandran Gary L. Miller, |
| Publisher : | N/A |
| Publication Date : | 1987 |
| ISSN : | N/A |
| Abstract : | We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called ?open ear decomposition?. A parallel implementation of the algorithm on a CRCW PRAM runs in O(log 2 n) parallel time using O(n + m) processors, where n is the number of vertices and m is the number of edges in the graph., |