Improved Parallel Algorithms for Finding the Most Vital Edge of A Graph with Respect to Minimum Spanning Tree.
Hong Shen · 1997
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 will cause the greatest weight-increase in the minimum spanning tree of the remaining graph. This paper presents fast parallel algorithms that compute the most vital edge of G in O(logn) time using O(m log log log n= log n+n) CRCW processors, and in O(logn log log n) time using O((m + n 2 = log n)= log log n) CREW processors, respectively. This improves the known results of O(log n) time and O(m) processors on CRCW PRAM [11, 13], and of O(n) time and O(n 2 = log 2 n) processors on CREW PRAM [13]. Keywords: Minimum spanning tree, most vital edge, parallel algorithm, PRAM. 1 Introduction Let G = (V; E) be a connected, undirected and weighted graph with vertex set V and edge set E, where jV j = n and jEj = m. Associated with each edge e there is a real valued weight w(e). Let MSTG be a minimum spanning tre...