Opened 11 years ago

Closed 11 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 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 11 years ago.
Revised version of Nathann's patch using the proper # optional syntax

Download all attachments as: .zip

Change History (12)

comment:1 Changed 11 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 11 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 11 years ago by mvngu

  • Description modified (diff)

comment:4 Changed 11 years ago by ncohen

  • Description modified (diff)

Patch rebased on top of #7608 !

comment:5 Changed 11 years ago by jason

  • Cc jason added

comment:6 Changed 11 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 11 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

comment:8 Changed 11 years ago by rlm

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

comment:9 Changed 11 years ago by ncohen

  • Status changed from needs_work to needs_review

Updated !

Changed 11 years ago by rlm

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

comment:10 Changed 11 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

Looks good to me.

comment:11 Changed 11 years ago by rlm

  • Merged in set to sage-4.5.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.