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

asked 10 years ago

Bart
3 ●1 ●2

updated 10 years ago

FrédéricC

5426 ●4 ●44 ●121

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?

add a comment

2 Answers

Sort by » oldest newest most voted

answered 10 years ago

slelievre
17779 ●22 ●162 ●352 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.

link

Comments

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

Bart ( 10 years ago )

add a comment

answered 10 years ago

Nathann
1615 ●2 ●15 ●36

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

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 ( 10 years ago )

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? savecancel

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?