Opened 11 years ago
Last modified 11 years ago
#7476 closed enhancement
Edge-disjoint spanning trees — at Version 3
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: |
Description (last modified by )
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.
This ticket might conflict with #7608. The patch at #7608 makes a lot of changes to sage/graphs/generic_graph.py, a module that is also touched by ncohen's patch on this ticket.
Change History (3)
comment:1 Changed 11 years ago by
- Report Upstream set to N/A
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
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 11 years ago by
- Description modified (diff)
Finally, it was pretty quick to do it through LP :-)
Nathann