4
$\begingroup$

Given an undirected weighted graph $G(V,E)$, where the number of edges is $|V|+10$, how can I find the minimum spanning tree of $G$ in $O(|V|)$?

Kruskal's algorithm is out of the question, since sorting alone is $O(|V|\log |V|)$, so I thought maybe using Prim's algorithm with minimum binary heap, but still - every iteration will cost $\log |V|$ for updating vertices keys in the heap, so altogether it's $|V|\log |V|$.
I know that the key here is to use the fact that $|E|=|V|+10$, so I start thinking maybe removing the 11 edges with the biggest weights, as long as the graph stays connected, but that's obviously a bad idea since it'll - again - require sorting.
I just can't figure it out. Any help would be greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ Why should you have to sort, to find $11$ edges? The only tricky part is to ignore bridges, but that should be linear too. $\endgroup$ – Karolis Juodelė Dec 23 '13 at 20:44
  • $\begingroup$ So, I need to find the $11$ biggest edges? But nothing says that none of the $11$ biggest edges will be in the spanning tree... It is possible that one of them will be, so throwing them away just like that (as long as they're not bridges) is not optimal. $\endgroup$ – so.very.tired Dec 23 '13 at 23:03
  • 1
    $\begingroup$ Look for "finding a cycle in an undirected graph". $\endgroup$ – Hendrik Jan Dec 23 '13 at 23:55
  • $\begingroup$ Finding all cycles in the graph, and removing the maximum edge from each cycle. would that work? $\endgroup$ – so.very.tired Dec 24 '13 at 13:48
2
$\begingroup$

Use DFS to find a cycle in the graph (in linear time). Save the maximum-weight edge while performing DFS, Delete it from the outputted cycle. Repeat 11 times. Done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.