ON FINDING SPARSE THREE-EDGE-CONNECTED AND THREE-VERTEX-CONNECTED SPANNING SUBGRAPHS

DOI10.1142/S012905411450018XzbMath1303.05187OpenAlexW1983758508MaRDI QIDQ2929622

Amr Elmasry, Yung Hyang 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

graph algorithmsdepth-first searchcut pairsparse spanning subgraphthree-edge-connected graphthree-vertex-connected graph

Mathematics Subject Classification ID

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

Cites Work

• A simple 3-edge-connected component algorithm
• 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
• A linear time algorithm for computing 3-edge-connected components in a multigraph
• Algorithms for placing monitors in a flow network
• PERFECT STOCHASTIC SUMMATION IN HIGH ORDER FEYNMAN GRAPH EXPANSIONS
• Efficient Planarity Testing
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: ON FINDING SPARSE THREE-EDGE-CONNECTED AND THREE-VERTEX-CONNECTED SPANNING SUBGRAPHS