Finding fundamental cycles and bridges on a tree-structured parallel computer
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.
- A parallel algorithm for constructing minimum spanning trees
- An \(n^ 2\) algorithm for determining the bridges of a graph
- Efficient parallel algorithms for some graph problems
- Fast, Efficient Parallel Algorithms for Some Graph Problems
- Graph algorithms on a tree-structured parallel computer
- scientific article; zbMATH DE number 3573250 (Why is no real title available?)
- Stirling networks: A versatile combinatorial topology for multiprocessor systems
- scientific article; zbMATH DE number 2089184 (Why is no real title available?)
- Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
- Graph algorithms on a tree-structured parallel computer
- A parallel algorithm for eliminating cycles in undirected graphs
This page was built for publication: Finding fundamental cycles and bridges on a tree-structured parallel computer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1093373)
