Parallel algorithms for connectivity problems in graph theory

DOI10.1080/00207168608803490MaRDI QIDQ3802645zbMATH OpenOpenAlexWikidataFDO

Authors Ratan K. Ghosh

Publication date 1986

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207168608803490

zbMATH Keywords

bridgescommon ancestorconnected graphfundamental set of cyclesParallel algorithmsstrong orientation

Mathematics Subject Classification ID

Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3930349
• Parallel algorithms for finding connected components of a graph
• Parallel algorithms for connectivity problems on interval graphs
• scientific article; zbMATH DE number 1057772
• A Simpler Parallel Algorithm for Graph Connectivity
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• scientific article; zbMATH DE number 3905859
• Efficient parallel algorithms for graph problems
• scientific article; zbMATH DE number 3972201
• An Asynchronous Parallel Algorithm for Undirected Graph Connectivity

Cites work

• A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs
• A note on finding the bridges of a graph
• A parallel search algorithm for directed acyclic graphs
• Algorithms for finding a fundamental set of cycles for an undirected linear graph
• An algorithm for finding a fundamental set of cycles of a graph
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Finding Dominators in Directed Graphs
• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• scientific article; zbMATH DE number 3606484 (Why is no real title available?)
• Parallel breadth-first search algorithms for trees and graphs
• Parallel strong orientation of an undirected graph

Cited in

(26)

• Finding fundamental cycles and bridges on a tree-structured parallel computer
• Parallel strong orientation on a mesh connected computer
• A fully-pipelined systolic algorithm for finding bridges on an undirected connected graph
• Parallel search algorithms for graphs and trees
• Efficient parallel algorithms for graph problems
• Approximating unweighted connectivity problems in parallel
• A faster parallel connectivity algorithm on cographs
• A faster parallel algorithm for k-connectivity
• scientific article; zbMATH DE number 2089184 (Why is no real title available?)
• Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• scientific article; zbMATH DE number 3914356 (Why is no real title available?)
• An Efficient Parallel Biconnectivity Algorithm
• scientific article; zbMATH DE number 3930349 (Why is no real title available?)
• Graph Problems on a Mesh-Connected Processor Array
• scientific article; zbMATH DE number 4068310 (Why is no real title available?)
• An 0(log n) parallel algorithm for strong connectivity augmentation problem
• Parallel Complexity of the Connected Subgraph Problem
• scientific article; zbMATH DE number 4115994 (Why is no real title available?)
• scientific article; zbMATH DE number 5879017 (Why is no real title available?)
• Parallel graph algorithms for hypercube computers
• Parameterized algorithms for finding highly connected solution
• Parameterized algorithms for finding highly connected solution
• Parallel strong orientation of an undirected graph
• Finding Euler tours in parallel
• A parallel algorithm for eliminating cycles in undirected graphs

This page was built for publication: Parallel algorithms for connectivity problems in graph theory

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