Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||CHAIN DECOMPOSITIONS OF 4-CONNECTED GRAPHS|
|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.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.