SIAM Journal on Computing · 2006 · 86 citations · 11 references
ComputingComputer ScienceAlgorithmsCombinatoricsComputer NetworksGraph AlgorithmsGraph TheoryNetwork ReliabilityNetwork TopologyCommunication ProtocolsConnectivity AlgorithmsDecompositionsSpanning Tree ConstructionTree Algorithms
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|^2)$ algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an $O(|V|^3)$ algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs.
11
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
John E. Hopcroft, Robert E. Tarjan · Journal of the ACM · 1974 · 1.1K citations · Full text
Avram Zehavi, Alon Itai · Journal of Graph Theory · 1989 · 131 citations