Fast, Efficient Parallel Algorithms for Some Graph Problems
From MaRDI portal
Publication:3932299
DOI10.1137/0210051zbMath0476.68036MaRDI QIDQ3932299
Carla D. Savage, Joseph F. Ja'Ja'
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210051
graph algorithm; fundamental cycle; minimum spanning tree; bridge; biconnected component; multiprocessing
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68W99: Algorithms in computer science
Related Items
FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS, PARALLEL BLOCK-FINDING USING DISTANCE MATRICES, Graph theory (algorithmic, algebraic, and metric problems), Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, A general program scheme for finding bridges, Parallel strong orientation of an undirected graph, A parallel search algorithm for directed acyclic graphs, Graph algorithms on a tree-structured parallel computer, An adaptive and cost-optimal parallel algorithm for minimum spanning trees, Combinatorial analysis (nonnegative matrices, algorithmic problems), Depth-first search is inherently sequential, An O(log n) algorithm for parallel update of minimum spanning trees, The parallel complexity of deadlock detection, Finding fundamental cycles and bridges on a tree-structured parallel computer, Fast parallel graph searching with applications, An efficient parallel algorithm for updating minimum spanning trees, Determining connected components in linear time by a linear number of processors, Parallel algorithms for the connected components and minimal spanning tree problems, Distributed processing of graphs: Fundamental cycles algorithm, Expected parallel time and sequential space complexity of graph and digraph problems, A new class of parallel algorithms for finding connected components on machines with bit-vector operations, A self-stabilizing algorithm for detecting fundamental cycles in a graph, An efficient distributed bridge-finding algorithm, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Optimal parallel algorithms for multiple updates of minimum spanning trees, On the parallel computation of the biconnected and strongly connected co-components of graphs, Parallel computations on graphs, New fast parallel algorithm for the connected component problem and its VLSI implementation, Equivalence in the complexity of several problems, Parallel algorithms for connectivity problems in graph theory
