Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

A two way minimum spanning tree of a directed graph

Given a directed graph with weighted edges, what algorithm can be used to give a sub-graph that has minimum weight, but allows movement from any vertex to any other vertex in the graph (under the assumption that paths between any two vertices always exist).

Does such an algorithm exist?

like image 450
Mantas Vidutis Avatar asked May 10 '10 06:05

Mantas Vidutis


1 Answers

Even though they weren't right themselves, taking the time to follow Vitalii's Wikipedia links quickly uncovered this algorithm:

http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm

like image 152
Mathew Avatar answered Nov 11 '22 22:11

Mathew



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!