Ask Your Question

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 gravatar image

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

FrédéricC gravatar image

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

2 Answers

Sort by » oldest newest most voted

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

slelievre gravatar image

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 more


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

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

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

Nathann gravatar image

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

edit flag offensive delete link more


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 gravatar imageBart ( 2014-07-29 09:48:41 +0100 )edit

Your Answer

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

Add Answer

Question Tools

1 follower


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

Seen: 553 times

Last updated: Jul 28 '14