Context Navigation

← Previous Ticket
Next Ticket →

#7476 closed enhancement (fixed)

Edge-disjoint spanning trees

Reported by:	ncohen	Owned by:	rlm
Priority:	major	Milestone:	sage-4.5
Component:	graph theory	Keywords:
Cc:	jason	Merged in:	sage-4.5.alpha1
Authors:	Nathann Cohen	Reviewers:	Robert Miller
Report Upstream:	N/A	Work issues:
Branch:		Commit:
Dependencies:		Stopgaps:

Description (last modified by ncohen)

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.

Attachments (1)

trac_7476.patch (8.3 KB) - added by rlm 9 years ago.: Revised version of Nathann's patch using the proper # optional syntax

Download all attachments as: .zip

Change History (12)

comment:1 Changed 9 years ago by ncohen

Report Upstream set to N/A
Status changed from new to needs_review

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

Nathann

comment:2 Changed 9 years ago by ncohen

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

comment:3 Changed 9 years ago by mvngu

Description modified (diff)

comment:4 Changed 9 years ago by ncohen

Description modified (diff)

Patch rebased on top of #7608 !

comment:5 Changed 9 years ago by jason

Cc jason added

comment:6 Changed 9 years ago by rlm

Status changed from needs_review to needs_work

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

comment:7 Changed 9 years ago by ncohen

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