Graph Problems on a Mesh-Connected Processor Array
- 26 June 1984
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 31 (3) , 649-667
- https://doi.org/10.1145/828.322449
Abstract
Algorithms that run in O(n) steps are given for solving a number of graph problems on an n x n array of processors. The problems considered include: finding the bridges and artiedation points of an undirected graph, findmg the length of a shortest cycle, finding a minimum spanning tree, and a number of other problems.Keywords
This publication has 6 references indexed in Scilit:
- Data broadcasting in SIMD computersIEEE Transactions on Computers, 1981
- The Parallel Recognition of Classes of GraphsIEEE Transactions on Computers, 1980
- Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers, 1979
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- Cellular arrays for the solution of graph problemsCommunications of the ACM, 1972
- A Theorem on Boolean MatricesJournal of the ACM, 1962