Opened 10 years ago
Closed 10 years ago
#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 )
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)
Change History (12)
comment:1 Changed 10 years ago by
- Report Upstream set to N/A
- Status changed from new to needs_review
comment:2 Changed 10 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 10 years ago by
- Description modified (diff)
comment:5 Changed 10 years ago by
- Cc jason added
comment:6 Changed 10 years ago by
- 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 10 years ago by
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
comment:8 Changed 10 years ago by
If you indicate in the ALGORITHM section where the papers are regarding the poly-time algorithm, I'm fine with including this.
comment:10 Changed 10 years ago by
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
Looks good to me.
comment:11 Changed 10 years ago by
- Merged in set to sage-4.5.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
Finally, it was pretty quick to do it through LP :-)
Nathann