Parallel Algorithms for Finding Cycles and Cutsets of Graphs

We first present VLSI algorithms that run in O(n 2 ) steps for finding (and reporting) a fundamental set of cycles and a fundamental set of cutsets of an undirected graph on an nxn mesh of processors (SIMD). Both algorithms are decomposable and run in O(n 4 =k 2 ) steps for a graph with n vertices when the size of the mesh-connected computer is kxk and k ! n. An idea similar to the one used in finding a fundamental set of cycles of an undirected graph yields an O(n 2 ) algorithm for generating shortest paths between all pairs of vertices of a graph on the same model. Then, we present a new and elegant cycle vector space algorithm that runs in O(n 2 \Delta ff) steps and needs O(n) space for enumerating all the cycles of a planar graph with n vertices, where ff is the total number of simple cycles in the graph. Unlike backtrack algorithms, cycle vector space algorithms for this problem are suitable for parallelization. A parallel version of this algorithm along with a parall..