Edge-disjoint spanning trees

[nathanncohen]

The theorem from Nash-Williams on the existence of k edge-disjoint spanning trees in a graph is both important, useful, and polynomial to compute. This could be implemented using the short proof described in the following article :

http://arxiv.org/abs/0911.2809

Or, if we achieve to eventually define in Sage a class Matroid, this could be done through the Matroid Union Theorem as presented in Schrijver's book.

CC: @jasongrout

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller

Merged: sage-4.5.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/7476

[nathanncohen]

comment:1

Finally, it was pretty quick to do it through LP :-)

Nathann

[nathanncohen]

comment:2

For an explanation of the Linear Program used to solve this problem, see the LP chapter from : http://code.google.com/p/graph-theory-algorithms-book/

Nathann

[nathanncohen]

comment:4

Patch rebased on top of #7608 !

[rlmill]

comment:6

I'd much rather see the algorithm in the paper implemented, especially if it's polynomial time.

[nathanncohen]

comment:7

What would you think of still putting this into Sage ? It would take much more time to write the other algorithm, and nothing says that LP would not be faster anyway...

Nathann

[rlmill]

comment:8

If you indicate in the ALGORITHM section where the papers are regarding the poly-time algorithm, I'm fine with including this.

[nathanncohen]

comment:9

Updated !

[rlmill]

Revised version of Nathann's patch using the proper # optional syntax

[rlmill]

Author: Nathann Cohen

[rlmill]

comment:10

Attachment: trac_7476.patch.gz

Looks good to me.

[rlmill]

Reviewer: Robert Miller

[rlmill]

Merged: sage-4.5.alpha1