Opened 11 years ago

Last modified 11 years ago

#7476 closed enhancement

Edge-disjoint spanning trees — at Initial Version

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

Status badges

Description

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.

Change History (0)

Note: See TracTickets for help on using tickets.