Edge-disjoint spanning trees and paths
When does an undirected graph, with given nodes s and t, contain k spanning trees and l s-t paths, all of which are edge-disjoint?
The problem is a very special case of the more difficult Steiner tree packing problem with different terminal sets, discussed by Grötschel, Martin and Weismantel .
- A. Bernáth, Z. Király, Finding edge-disjoint subgraphs in graphs, EGRES Quick Proofs QP-2010-04
- A. Bernáth, Z. Király, On the tractability of some natural packing, covering and partitioning problems, EGRES Technical Report no. 2011-05, arXiv link
- M. Grötschel, A. Martin, R. Weismantel, Packing Steiner trees: polyhedral investigations, DOI link