Fast, Efficient Parallel Algorithms for Some Graph Problems

DOI10.1137/0210051MaRDI QIDQ3932299zbMATH OpenOpenAlexFDO

Authors Carla D. Savage, Joseph 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

minimum spanning treegraph algorithmbridgebiconnected componentfundamental cyclemultiprocessing

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)

Cited in

(30)

• Parallel algorithms for connectivity problems in graph theory
• The parallel complexity of deadlock detection
• Finding fundamental cycles and bridges on a tree-structured parallel computer
• An efficient parallel algorithm for updating minimum spanning trees
• Equivalence in the complexity of several problems
• Determining connected components in linear time by a linear number of processors
• Fast parallel graph searching with applications
• An efficient distributed bridge-finding algorithm
• FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS
• PARALLEL BLOCK-FINDING USING DISTANCE MATRICES
• Graph theory (algorithmic, algebraic, and metric problems)
• A self-stabilizing algorithm for detecting fundamental cycles in a graph
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• Optimal parallel algorithms for multiple updates of minimum spanning trees
• Combinatorial analysis (nonnegative matrices, algorithmic problems)
• Depth-first search is inherently sequential
• Parallel algorithms for the connected components and minimal spanning tree problems
• On the parallel computation of the biconnected and strongly connected co-components of graphs
• Parallel strong orientation of an undirected graph
• New fast parallel algorithm for the connected component problem and its VLSI implementation
• A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
• Distributed processing of graphs: Fundamental cycles algorithm
• An adaptive and cost-optimal parallel algorithm for minimum spanning trees
• A general program scheme for finding bridges
• Expected parallel time and sequential space complexity of graph and digraph problems
• A parallel search algorithm for directed acyclic graphs
• Graph algorithms on a tree-structured parallel computer
• An O(log n) algorithm for parallel update of minimum spanning trees
• Parallel computations on graphs
• A new class of parallel algorithms for finding connected components on machines with bit-vector operations

This page was built for publication: Fast, Efficient Parallel Algorithms for Some Graph Problems

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