×

Finding a smooth frame decomposition of a graph. (English) Zbl 0993.05115

Summary: Let \(G\) be a graph and \(A\) be a subset of the edges of \(G\). A frame decomposition of \(G\) is a pair \((G-A,A)\) such that \(G-A\) is connected. A smooth frame decomposition of \(G\) is a frame decomposition satisfying the two conditions: (1) every leaf of \(G-A\) has a connected cotree, and (2) the set of bridges of \(G- B(G-A)\) is \(A\), where \(B(G- A)\) is the set of bridges of \(G-A\). An efficient algorithm for finding a smooth frame decomposition of a graph is provided.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite