How to use Sage to find a pair of vertex-disjoint paths of minimal total length?

asked 2014-07-28 15:15:00 +0100

Bart
3 ●1 ●2

updated 2015-01-14 14:10:13 +0100

5311 ●4 ●44 ●118

I want to find a pair of vertex-disjoint (s,t)-paths with minimal total length in a graph G, where the length is the sum of the edge weights of the paths. For this I would like to use the Suurballe and Tarjan Algorithm, but it seems to be a hidden (if I am right?) method. Is there any way I can still use this algorithm other than reprogram it myself?

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2014-07-28 17:52:17 +0100

slelievre
17724 ●22 ●160 ●351 http://carva.org/samue...

Suurballe and Tarjan's algorithm is the object of Sage trac ticket #13380, which has not made its way into Sage yet. You could try applying the patches found at that ticket. Maybe your question will revive the work on that ticket.

edit flag offensive delete link

Comments

Hm, I was already afraid of that. Thank you for clarification.

Bart ( 2014-07-29 09:49:27 +0100 )edit

add a comment

answered 2014-07-28 18:00:12 +0100

Nathann
1615 ●2 ●15 ●36

The easiest seems to rewrite this problem as an integer linear program.

edit flag offensive delete link

Comments

This would indeed be my next step, but I hoped that the Suurballe and Tarjan algorithm would work. It would save some time. Thank you for your suggestion.

Bart ( 2014-07-29 09:48:41 +0100 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

How to use Sage to find a pair of vertex-disjoint paths of minimal total length?

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

How to use Sage to find a pair of vertex-disjoint paths of minimal total length? edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

How to use Sage to find a pair of vertex-disjoint paths of minimal total length?