1992 · 40 citations · 22 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisComputational ComplexityData ParallelismGraph AlgorithmsGraph TheoryParallel Complexity TheoryEar DecompositionMinimum Spanning Tree AlgorithmsMinimum Spanning Tree ProblemParallel Algorithm AnalysisParallel Algorithm ComplexityParallel Graph AlgorithmsParallel Minimum Spanning TreeParallel Minimum Spanning Tree Algorithms
We present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph G = (V;E) of n = jV j vertices andm = jEj edges on an EREW PRAM in O(log3=2n) time using n+m processors. This represents a substantial improvement in the running time over the previous results for this problem using at the same time the weakest of the PRAM models. It also implies the existence of algorithms having the same complexity bounds for the EREW PRAM, for connectivity, ear decomposition, biconnectivity, strong orientation, st-numbering and Euler tours problems.
22
Richard Cole · SIAM Journal on Computing · 1988 · 734 citations
An Efficient Parallel Biconnectivity Algorithm
Robert E. Tarjan, Uzi Vishkin · SIAM Journal on Computing · 1985 · 526 citations
Efficient parallel algorithms for some graph problems
Francis Y. L. Chin, John Lam, I-Ngo Chen · Communications of the ACM · 1982 · 207 citations · Full text