Fast, Efficient Parallel Algorithms for Some Graph Problems

DOI10.1137/0210051zbMath0476.68036OpenAlexW2020810308MaRDI 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

zbMATH Keywords

graph algorithmfundamental cycleminimum spanning treebridgebiconnected componentmultiprocessing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Related Items

An O(log n) algorithm for parallel update of minimum spanning trees, A new class of parallel algorithms for finding connected components on machines with bit-vector operations, Optimal parallel algorithms for multiple updates of minimum spanning trees, Equivalence in the complexity of several problems, The parallel complexity of deadlock detection, Finding fundamental cycles and bridges on a tree-structured parallel computer, An efficient distributed bridge-finding algorithm, On the parallel computation of the biconnected and strongly connected co-components of graphs, 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, FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS, PARALLEL BLOCK-FINDING USING DISTANCE MATRICES, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Parallel computations on graphs, Parallel algorithms for the connected components and minimal spanning tree problems, Parallel algorithms for connectivity problems in graph theory, Distributed processing of graphs: Fundamental cycles algorithm, Expected parallel time and sequential space complexity of graph and digraph problems, Graph theory (algorithmic, algebraic, and metric problems), New fast parallel algorithm for the connected component problem and its VLSI implementation, A self-stabilizing algorithm for detecting fundamental cycles in a graph, 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