Finding fundamental cycles and bridges on a tree-structured parallel computer (Q1093373)

We present parallel algorithms for finding fundamental cycles and bridges in a connected, undirected graph G with n vertices. The machine model that we are concerned with is a tree-structured parallel computer which combines SIMD and systolic computers in a treelike manner. Under this model, we have an \(O(n^ 2d/p+n \log p)\)-time algorithm for finding fundamental cycles and an \(O(n^ 2/p)\)-time algorithm for finding bridges, where p (1\(\leq p\leq n)\) is the number of processing elements used and d is the depth of a breadth-first spanning tree of G.