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

DOI10.1109/TC.1987.1676869zbMath0643.94044OpenAlexW1821591339MaRDI QIDQ3786431

No author found.

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 algorithmsundirected graphspanning trees

Mathematics Subject Classification ID

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

Related Items (21)

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

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