Parallel algorithms for connectivity problems in graph theory
- 1 January 1986
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 18 (3-4) , 193-218
- https://doi.org/10.1080/00207168608803490
Abstract
Parallel algorithms for finding a fundamental set of cycles of a graph, for locating the bridges of a connected graph and for strongly orienting a bridgeless connected graph are proposed in this paper. Each of these algorithms runs in time and requires 0(n(m – n+ 1)) processors on a shared memory model of a single instruction-stream multiple data-stream computer, where m and n refer respectively to the number of arcs and the number nodes of the underlying graph. The running time of the algorithms is reduced to provided 0(n 3) processors are used, where d refers to the diameter of the graph.Keywords
This publication has 9 references indexed in Scilit:
- A parallel search algorithm for directed acyclic graphsBIT Numerical Mathematics, 1984
- Parallel strong orientation of an undirected graphInformation Processing Letters, 1984
- Parallel breadth-first search algorithms for trees and graphsInternational Journal of Computer Mathematics, 1984
- Fast, Efficient Parallel Algorithms for Some Graph ProblemsSIAM Journal on Computing, 1981
- A note on finding the bridges of a graphInformation Processing Letters, 1974
- Finding Dominators in Directed GraphsSIAM Journal on Computing, 1974
- An algorithm for finding a fundamental set of cycles of a graphCommunications of the ACM, 1969
- Algorithms for finding a fundamental set of cycles for an undirected linear graphCommunications of the ACM, 1967
- A Mechanical Analysis of the Cyclic Structure of Undirected Linear GraphsJournal of the ACM, 1966