Graph algorithms on a tree-structured parallel computer |
| |
| Authors: | D. Y. Yeh D. T. Lee |
| |
| Affiliation: | (1) Department of Computer and Information Science, Cleveland State University, 44115 Cleveland, Ohio, USA;(2) Department of Electrical Engineering and Computer Science, Northwestern University, 60201 Evanston, Illinois, USA |
| |
| Abstract: | Parallel algorithms for some graph-theoretic problems on a tree-structured computer are presented. In particular, ifp denotes the number of processing elements, algorithms that run inO(n2/p) time for finding connected components, transitive closure and the minimum spanning tree of an undirected graph withn vertices are obtained. |
| |
| Keywords: | SIMD computer systolic computer parallel algorithm graph algorithm time complexity |
| 本文献已被 SpringerLink 等数据库收录！ |
|
