A linear time algorithm for computing 3-edge-connected components in a multigraph
type: Item
instance of: scholarly article
title: A linear time algorithm for computing 3-edge-connected components in a multigraph
zbMATH Open document ID: 0761.05089
DOI: 10.1007/BF03167564
author: Hiroshi Nagamochi
author: Toshihide Ibaraki
published in: Japan Journal of Industrial and Applied Mathematics
publication date: 1993-01-16T00:00:00Z
review text: 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.
reviewed by: Bai Kishan Dass
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 94849
zbMATH Keywords: linear time algorithm
zbMATH Keywords: 3-edge-connected components
zbMATH Keywords: multigraph
zbMATH Keywords: edge- connectivity
zbMATH Keywords: maximum flows
zbMATH Keywords: forests
zbMATH Keywords: depth-first search
zbMATH Keywords: time analysis
MaRDI profile type: Publication
cites work: On computing the connectivities of graphs and digraphs
cites work: Augmentation Problems
cites work: Network Flow and Testing Graph Connectivity
cites work: On sparse subgraphs preserving connectivity properties
cites work: Finding the Vertex Connectivity of Graphs
cites work: Dividing a Graph into Triconnected Components
cites work: Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
cites work: Q3140458
cites work: A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
cites work: Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
cites work: Counting the number of minimum cuts in undirected multigraphs
cites work: \(k\)-connectivity and decomposition of graphs into forests
cites work: Bottlenecks and Edge Connectivity in Unsymmetrical Networks
cites work: Depth-First Search and Linear Graph Algorithms
description: scientific article; zbMATH DE number 94849