On finding sparse three-edge-connected and three-vertex-connected spanning subgraphs

DOI10.1142/S012905411450018XMaRDI QIDQ2929622zbMATHOpenAlexFDO

Authors Amr Elmasry, Yung H. Tsin

Publication date 14 November 2014

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s012905411450018x

zbMATH Keywords

depth-first searchgraph algorithmscut pairsparse spanning subgraphthree-edge-connected graphthree-vertex-connected graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Connectivity (05C40) Density (toughness, etc.) (05C42)

Recommendations

• Generating 3-vertex connected spanning subgraphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
• An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph
• A simple 3-edge-connected component algorithm

Cites work

• A linear time algorithm for computing 3-edge-connected components in a multigraph
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A simple 3-edge-connected component algorithm
• Algorithms for placing monitors in a flow network
• Depth-First Search and Linear Graph Algorithms
• Efficient Planarity Testing
• PERFECT STOCHASTIC SUMMATION IN HIGH ORDER FEYNMAN GRAPH EXPANSIONS
• Yet another optimal algorithm for 3-edge-connectivity

Cited in

(4)

• Generating 3-vertex connected spanning subgraphs
• Spanning even subgraphs of 3‐edge‐connected graphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Why depth-first search efficiently identifies two and three-connected graphs

This page was built for publication: On finding sparse three-edge-connected and three-vertex-connected spanning subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2929622)