Exercises Videos Notes Multiple-choice questions Apps

Related books

Algorithms Chromatic Graph Theory Algorithm Design Graph Coloring Problems Suggest a Book
2

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:
Printable version LaTeX source
delete flag offensive retag edit

posted Aug 24 '12

rizwanhudda gravatar image 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