On the parallel computation of the biconnected and strongly connected co-components of graphs

DOI10.1016/j.dam.2007.03.016zbMath1123.05086OpenAlexW2154591915MaRDI QIDQ2383544

Leonidas Palios, Stavros D. Nikolopoulos

Publication date: 19 September 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.03.016

zbMATH Keywords

parallel algorithmsbiconnected and co-biconnected componentsco-biconnectivity algorithmsstrong co-connectivity algorithmsstrongly connected and co-connected components

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Depth-first search is inherently sequential
• An improved parallel algorithm that computes the BFS numbering of a directed graph
• Parallel algorithms for the connected components and minimal spanning tree problems
• Faster optimal parallel prefix sums and list ranking
• Improving the efficiency of parallel minimum spanning tree algorithms
• An optimal parallel co-connectivity algorithm
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• An Efficient Parallel Biconnectivity Algorithm
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• Computing connected components on parallel computers
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Efficient parallel algorithms for some graph problems
• An O(logn) parallel connectivity algorithm
• Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation