Finding the most vital edge with respect to minimum spanning tree in weighted graphs (Q1183410)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding the most vital edge with respect to minimum spanning tree in weighted graphs |
scientific article |
Statements
Finding the most vital edge with respect to minimum spanning tree in weighted graphs (English)
0 references
28 June 1992
0 references
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.
0 references
minimum spanning tree
0 references