Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/66963
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
numbering
independent trees
algorithm
Country: EUA
Editor: Siam Publications
Rights: aberto
Identifier DOI: 10.1137/S0097539703436734
Date Issue: 2006
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

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.