A new graph triconnectivity algorithm and its parallelization |
| |
| Authors: | Gary L. Miller Vijaya Ramachandran |
| |
| Affiliation: | (1) School of Computer Science, Carnegie Mellon University, 15213 Pittsburgh, PA, USA;(2) Department of Computer Sciences, University of Texas, 78712 Austin, TX, USA |
| |
| 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 inO(log2n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109. |
| |
| Keywords: | 05 C 40 05 C 85 68 Q 20 68 Q 22 68 Q 25 68 R 10 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
