On finding sparse three-edge-connected and three-vertex-connected spanning subgraphs
DOI10.1142/S012905411450018XzbMATH Open1303.05187OpenAlexW1983758508MaRDI QIDQ2929622FDOQ2929622
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
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
depth-first searchgraph algorithmscut pairsparse spanning subgraphthree-edge-connected graphthree-vertex-connected graph
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)
Cites Work
- Depth-First Search and Linear Graph Algorithms
- A linear time algorithm for computing 3-edge-connected components in a multigraph
- Efficient Planarity Testing
- Yet another optimal algorithm for 3-edge-connectivity
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- PERFECT STOCHASTIC SUMMATION IN HIGH ORDER FEYNMAN GRAPH EXPANSIONS
- A simple 3-edge-connected component algorithm
- Algorithms for placing monitors in a flow network
Cited In (4)
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)
