Suggest a Book

# Second Minimum spanning tree

Given an weighted undirected graph $G = (V, E)$, and $w : E \mapsto R^+$.

• Let T be MST i,e minimum spanning tree of graph G.
• Second MST is a Tree T' different from T, and its weight is less than weights of all other spanning trees of G except T.

Find the Second MST of an input graph in $O(|E|\log{|E|})$ time.

NOTE: There is also an O(|E|) solution to this which is quite complicated.

Level:
delete retag edit

posted Aug 24 '12

rizwanhudda
31 1 5
POST AN EXERCISE POST A VIDEO POST NOTES POST MULTIPLE-CHOICE QUESTION

## Stats

Posted: Aug 24 '12

Seen: 157 times

Last updated: Aug 24 '12