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

DOI10.1142/S012905411450018XzbMath1303.05187MaRDI 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)

zbMATH Keywords

graph algorithms; depth-first search; cut pair; sparse spanning subgraph; three-edge-connected graph; three-vertex-connected graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

05C42: Density (toughness, etc.)