GraphStream Users

Archives de la liste Aide


Spanning tree on oriented graph.


Chronologique Discussions 
  • From: <nicolas.quattropani AT gmail.com>
  • To: graphstream-users AT litislab.fr
  • Subject: Spanning tree on oriented graph.
  • Date: Tue, 14 Jun 2011 15:48:00 +0200 (CEST)

Hi,

I am currently working on spanning trees and I encountered a problem with the
oriented graphs which is that Kruskal and Prim algorithm can't be applied on
them. My research to solve this problem leads me to the Edmond's algorithm. It
could be used to find minimum optimum branchings which is basically what I
would like to do on oriented graphs.

Are there any solutions to overcome this problem or the only thing to do is to
implement Edmond's or Trajan's algorithim ?
In that case, what would be the major encountered issues if I tried to
implement one of these algorithms ?

Here are some useful links about these algos and their code is under the MIT
licence :

- Edmond's algo :
http://algowiki.net/wiki/index.php?title=Edmonds%27s_algorithm
- Tarjan's algo :
http://algowiki.net/wiki/index.php?title=Tarjan%27s_algorithm
- Wikipedia : http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm

Nicolas



Archives gérées par MHonArc 2.6.16.

Top of page