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
• DOI: 10.1006/jpdc.1997.1383

✦ 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.