Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||Finding four independent trees|
|Abstract:||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(vertical bar V vertical bar(2)) algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an O(vertical bar V vertical bar(3)) algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs.|
|Citation:||Siam Journal On Computing. Siam Publications, v. 35, n. 5, n. 1023, n. 1058, 2006.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.