Finding the most vital edge with respect to minimum spanning tree in weighted graphs (Q1183410): Difference between revisions

Let \(g(G)\) denote the weight of a minimum spanning tree of \(G\) if \(G\) is connected; otherwise, \(g(G)=\infty\). An edge \(e\) is called a most vital edge (MVE) in \(G\) if \(g(G-e)\geq g(G-e')\) for every edge \(e'\) of \(G\). The problem of finding such an edge is called the 1-MVE problem. Two algorithms with time complexities O(\(q\log q\)) and O(\(p^ 2\)) are presented for solving the 1-MVE problem.