Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Finding four independent trees
Author: Curran, S
Lee, O
Yu, XX
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.
Subject: connectivity
chain decomposition
independent trees
Country: EUA
Editor: Siam Publications
Citation: Siam Journal On Computing. Siam Publications, v. 35, n. 5, n. 1023, n. 1058, 2006.
Rights: aberto
Identifier DOI: 10.1137/S0097539703436734
Date Issue: 2006
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000236805200002.pdf441.66 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.