New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM

DOI10.1109/TC.1987.1676869MaRDI QIDQ3786431zbMATH OpenOpenAlexFDO

Authors

Publication date 1987

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tc.1987.1676869

zbMATH Keywords

connected componentsparallel algorithmsspanning treesundirected graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Cited in

(21)

• On efficient parallel strong orientation
• Separation and lower bounds for ROM and nondeterministic models of parallel computation
• A linear systolic algorithm for the connected component problem
• Maintaining bridge-connected and biconnected components on-line
• A new class of parallel algorithms for finding connected components on machines with bit-vector operations
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• Improving the efficiency of parallel minimum spanning tree algorithms
• A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs
• A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
• Optimal parallel verification of minimum spanning trees in logarithmic time
• On the parallel computation of the biconnected and strongly connected co-components of graphs
• New fast parallel algorithm for the connected component problem and its VLSI implementation
• On the Strongly Connected and Biconnected Components of the Complement of Graphs
• An optimal parallel algorithm for minimum spanning trees in planar graphs
• Adapting parallel algorithms to the W-stream model, with applications to graph problems
• PARALLEL BLOCK-FINDING USING DISTANCE MATRICES
• Graph connectivity in log steps using label propagation
• Distributed MST for constant diameter graphs
• The Swendsen–Wang dynamics on trees
• Resource bounds for parallel computation of threshold and symmetric functions
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms

This page was built for publication: New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM

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