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

DOI10.1016/J.DAM.2007.03.016MaRDI QIDQ2383544zbMATH OpenOpenAlexFDO

Authors Stavros D. Nikolopoulos, Leonidas Palios

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

biconnected and co-biconnected componentsco-biconnectivity algorithmsparallel algorithmsstrong co-connectivity algorithmsstrongly connected and co-connected components

Mathematics Subject Classification ID

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

Recommendations

• On the Strongly Connected and Biconnected Components of the Complement of Graphs
• An optimal parallel co-connectivity algorithm
• An Efficient Parallel Biconnectivity Algorithm
• An efficient and fast parallel-connected component algorithm
• Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components

Cites work

• An Efficient Parallel Biconnectivity Algorithm
• An improved parallel algorithm that computes the BFS numbering of a directed graph
• An O(logn) parallel connectivity algorithm
• An optimal parallel co-connectivity algorithm
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Computing connected components on parallel computers
• Depth-first search is inherently sequential
• Efficient and practical algorithms for sequential modular decomposition
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• Efficient parallel algorithms for some graph problems
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Faster optimal parallel prefix sums and list ranking
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3576688 (Why is no real title available?)
• scientific article; zbMATH DE number 1753166 (Why is no real title available?)
• Improving the efficiency of parallel minimum spanning tree algorithms
• Introduction to algorithms
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• Parallel algorithms for the connected components and minimal spanning tree problems

Cited in

(6)

• Why should biconnected components be identified first
• An optimal parallel co-connectivity algorithm
• scientific article; zbMATH DE number 5863491 (Why is no real title available?)
• Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
• The impact of a bi-connected graph decomposition on solving cooperative path-finding problems
• scientific article; zbMATH DE number 5879017 (Why is no real title available?)

This page was built for publication: On the parallel computation of the biconnected and strongly connected co-components of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2383544)