Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree

Let G be a connected, undirected and weighted graph with n vertices and m edges. A most vital edge of G with respect to minimum spanning tree is an edge whose removal from G results in the greatest weight-increase in the minimum spanning tree of the remaining graph. This paper presents a fast parallel algorithm that computes the most vital edge of G in O(log n) time using O(max{n, m log log log n/log n}) processors on a CRCW PRAM and O(log nlog log n) time using O(max{m, n²/(log n log log n)}) processors on an EREW PRAM respectively. It significantly improves the known results of O(log n) time and O(m) processors on the CRCW PRAM, and of O(log²n) time and O(n²/log²n) processors on the CREW PRAM, and O(n^1+ε) time using n^1-ε processors and O(m log(m/N)/N + nα(m, n)log(m/n)) time using N ≤ m log m/(nα(m, n)log(m/n)) processors on the EREW PRAM, respectively.