Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/62663
Type: Artigo de periódico
Title: CHAIN DECOMPOSITIONS OF 4-CONNECTED GRAPHS
Author: Curran, S
Lee, O
Yu, XX
Abstract: In this paper we give a decomposition of a 4-connected graph G into nonseparating chains, which is similar to an ear decomposition of a 2-connected graph. We also give an O(vertical bar V (G)vertical bar(2)vertical bar E (G)vertical bar) algorithm that constructs such a decomposition. In applications, the asymptotic performance can often be improved to O(vertical bar V (G)vertical bar(3)). This decomposition will be used to find four independent spanning trees in a 4-connected graph.
Subject: connectivity
nonseparating
good chain
chain decomposition
algorithm
Country: EUA
Editor: Siam Publications
Rights: aberto
Identifier DOI: 10.1137/S0895480103434592
Date Issue: 2005
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000208043500002.pdf422.26 kBAdobe PDFView/Open


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