A linear time algorithm for computing 3-edge-connected components in a multigraph (Q1199755)

In this paper, a linear time algorithm has been presented for computing all 3-edge-connected components in a given multigraph. The algorithm is based on a recent notion of decomposing a graph into forests to find a \(k\)-edge-connected spanning subgraph satisfying certain conditions. Properties of this decomposition have already been studied and applied to a variety of graph connectivity problems. The linear time algorithm presented in this paper has been obtained by combining this with depth- first search and with the time analysis.