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:

Status badges

Description (last modified by mvngu)

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 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)
Note: See TracTickets for help on using tickets.