File Exchange

image thumbnail

Edmonds algorithm

version 1.0 (5.8 KB) by

An implementation of Edmond's algorithm to obtain the maximum spanning weight tree from a graph.

3 Downloads

Updated

View License

Folks,
This is an implementation of the Edmond's algorithm taken from Alan Gibbons book algorithmic graph theory to obtain
a maximum weight spanning tree or a maximum branching.

I fixed a few mistakes in the published algorithm and have made this implementation available.

I believe you should be able to obtain the minimum spanning tree too by changing weights and changing them back after the application of the algorithm.

Comments and Ratings (2)

Hayro

Hayro (view profile)

What's the complexity of the algorithm?
Is it the same as with "graphmaxflow(G, SNode, TNode)" for which it says "The algorithm that determines Cut, all minimum cuts, has a time complexity of O(2^N), where N is the number of nodes. If this information is not needed, use the graphmaxflow function without the third output."

hanieh

hanieh (view profile)

MATLAB Release
MATLAB 7.6 (R2008a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video