๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Parallel Algorithm for Finding the Most Vital Edge in Weighted Graphs

โœ Scribed by Sudarshan Banerjee; Sanjeev Saxena


Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
75 KB
Volume
46
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis


Let G = (V, E) be a weighted undirected graph with n vertices and m edges; each edge e has a weight w(e) assigned to it. Let f(G) be the weight of a minimum spanning tree of G if G is connected; otherwise f(G) = โˆž. The most vital edge of G is an edge e such that f(Ge) โ‰ฅ f(G -eโ€ฒ) for every other edge eโ€ฒ of G. In this paper we describe an O(log n) time parallel algorithm with m processors for finding the most vital edge of a graph on the concurrent read exclusive write (CREW) model of parallel computation.


๐Ÿ“œ SIMILAR VOLUMES