A linear time algorithm for computing 3-edge-connected components in a multigraph
From MaRDI portal
Publication:1199755
DOI10.1007/BF03167564zbMath0761.05089MaRDI QIDQ1199755
Toshihide Ibaraki, Hiroshi Nagamochi
Publication date: 16 January 1993
Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)
multigraph; linear time algorithm; depth-first search; forests; maximum flows; time analysis; edge- connectivity; 3-edge-connected components
Related Items
AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY, A linear time algorithm for computing 3-edge-connected components in a multigraph, Canonical cactus representation for miminum cuts, Linear time algorithms for graph search and connectivity determination on complement graphs.
Cites Work
- Unnamed Item
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A linear time algorithm for computing 3-edge-connected components in a multigraph
- \(k\)-connectivity and decomposition of graphs into forests
- Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
- Bottlenecks and Edge Connectivity in Unsymmetrical Networks
- On computing the connectivities of graphs and digraphs
- Finding the Vertex Connectivity of Graphs
- Counting the number of minimum cuts in undirected multigraphs
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Network Flow and Testing Graph Connectivity
- Augmentation Problems
- On sparse subgraphs preserving connectivity properties
- Dividing a Graph into Triconnected Components
- Depth-First Search and Linear Graph Algorithms
