FINDING FOUR INDEPENDENT TREES.

Motivated by a multitree approach to the design of reliable communication protocols, Itai and Rodeh gave a linear time algorithm for finding two independent spanning trees in a 2-connected graph. Cheriyan and Maheshwari gave an O(∣V∣²) algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an O(∣V∣³) algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs. [ABSTRACT FROM AUTHOR]