GraphStream Users

Archives de la liste Aide


Re: Spanning tree on oriented graph.


Chronologique Discussions 
  • From: guilhelm savin <guilhelm.savin AT gmail.com>
  • To: graphstream-users AT litislab.fr
  • Subject: Re: Spanning tree on oriented graph.
  • Date: Tue, 14 Jun 2011 20:08:29 +0200
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; b=m8H6RybQEEYZTiqaYBp5Lh43eS6RSuYUjNbvr8apIwqMOMqqsZSnxxvyLuYtKP5LHV D16CBojL/UasPGt66PY29z3T+ZiY6U92zZHI4o4/OmFDq+ZeykkkTlgWUMMDsflvXWmf LvPsoYFfu/BB4sT40ikunlGQrkStQf8UERB4g=

Hi Nicolas,

Indeed Kruskal and Prim algorithm have to be applied to
non-oriented graphs.

I will try to have a look on Edmond and Tarjan algorithms
and maybe implements it in GraphStream.

Regards.


2011/6/14 <nicolas.quattropani AT gmail.com>
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



--
Guilhelm Savin
PhD Student of Computer Science




Archives gérées par MHonArc 2.6.16.

Top of page