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

DOI10.1007/BF03167564zbMath0761.05089MaRDI QIDQ1199755

Hiroshi Nagamochi, Toshihide Ibaraki

Publication date: 16 January 1993

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

multigraphlinear time algorithmdepth-first searchforestsmaximum flowstime analysisedge- connectivity3-edge-connected components

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Canonical cactus representation for miminum cuts, ON FINDING SPARSE THREE-EDGE-CONNECTED AND THREE-VERTEX-CONNECTED SPANNING SUBGRAPHS, Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs, Generically globally rigid zeolites in the plane, A simple certifying algorithm for 3-edge-connectivity, Certifying 3-edge-connectivity, A linear time algorithm for computing 3-edge-connected components in a multigraph, Yet another optimal algorithm for 3-edge-connectivity, Unnamed Item, AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY, Linear time algorithms for graph search and connectivity determination on complement graphs., A simple 3-edge connected component algorithm revisited, An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure

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