Ask Your Question
0

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

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

Bart gravatar image

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

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
1

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

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

Comments

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

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

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

Nathann gravatar image

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

edit flag offensive delete link more

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

Stats

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

Seen: 627 times

Last updated: Jul 28 '14