Chain Decompositions of 4-Connected Graphs | Zendy

Sean Curran | Zendy; Orlando Lee | Zendy; Xingxing Yu | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Chain Decompositions of 4-Connected Graphs

Author(s) -

Sean Curran,

Orlando Lee,

Xingxing Yu

Publication year - 2005

Publication title -

siam journal on discrete mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.843

H-Index - 66

eISSN - 1095-7146

pISSN - 0895-4801

DOI - 10.1137/s0895480103434592

Subject(s) - mathematics , combinatorics , decomposition , modular decomposition , graph , connected component , connectivity , spanning tree , discrete mathematics , line graph , pathwidth , ecology , biology

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research