1
$\begingroup$

I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.

$\endgroup$
  • $\begingroup$ Some 3-edge connected graphs don't have three edge-disjoint spanning trees. Consider G=(V,E) where V={a, b, c, d, e, f} and E={(a, b), (a, c), (a, d), (a, e), (b, f), (c, f), (d, f), (e, f), (b, c), (d, e)}. I believe it is 3-edge connected, but has six vertices and only ten edges, so cannot have three edge-disjoint spanning trees. (As each spanning tree would have five distinct edges.) $\endgroup$ – Neal Young Jul 26 '18 at 16:18
  • $\begingroup$ p.s. conditions for a graph to have k edge-disjoint spanning trees appear to be well studied. see e.g. math.wvu.edu/~hjlai/Pdf/Catlin_Pdf/Catlin49a.pdf . $\endgroup$ – Neal Young Jul 26 '18 at 16:51
1
$\begingroup$

The problem can be reduced to the edge orientation problem. Where if tree width (number of independent trees) is c, we need to orient the edges such that each vertex has an outdegree of at most c.

For planar graphs, where c = 3, an O(n log n) algorithm is given by [1]. For general graphs, a simple O(m + n) time algorithm computing a (2c - 1) orientation is shown in [2]. Other algorithms computing exact c orientation are harder including [3] and [4].

[1] Grossi and Lodi. Simple planar graph partition into three forests. Discrete Applied Mathematics, 84:121-132, 1998.

[2] Srinivasa R. Arikati, Anil Maheshwari, and Christos D. Zaroliagis. Efficient computation of implicit representations of sparse graphs. Discrete Applied Mathematics, 78:1-16,1997.

[3] Harold N. Gabow and Herbert H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7:465-497, 1992.

[4] J. C. Picard and M. Queyranne. A network flow soloution to some non-linear 0-1 programming problems, with applications to graph theory. Networks, 12:141-160, 1982.

$\endgroup$
  • $\begingroup$ i am worried if these methods will return spanning trees or not? $\endgroup$ – user5679384 Apr 27 '18 at 13:34
  • $\begingroup$ From c forest decomposition you can trivially get c edge orientation, by rooting each tree in every forest and assign parental edge to a vertex. The other direction gives you only a 2c forest decomposition from c edge orientation. The main problem is the formation of cycles as you compute the forest decomposition. $\endgroup$ – sbzk Jun 19 '18 at 13:15
  • $\begingroup$ Consider the 2c forests. For each vertex, add its i^{th} out edge in 2i^{th} (or (2i-1)^{th}) forest based on whether the index of its out neighbour is lower (or higher) than itself. As a result, each even indexed forest have only edges pointing from higher index to lower index and vice versa for odd indexed forests. This ensures that no cycles are present in a forest. $\endgroup$ – sbzk Jun 19 '18 at 13:18
  • $\begingroup$ For c=1, at least, a graph can have |V|-1 edges and a spanning tree, but not have any way of orienting the edges so that each edge has out-degree 1 (which requires |V| edges). So it might be clearer to say in the answer what reduction you have in mind by when you write "can be reduced to..." $\endgroup$ – Neal Young Jul 26 '18 at 17:12
  • $\begingroup$ Right updated, the out-degree has to be upper bounded by c. It can be less as well but never greater than c. $\endgroup$ – sbzk Jul 30 '18 at 8:47

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.