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