A polynomial time algorithm for cyclic vertex connectivity of cubic graphs

DOI10.1080/00207160.2016.1210792zbMath1367.05120OpenAlexW2460876635MaRDI QIDQ4976338

Jun Liang, Zan-Bo Zhang, Dingjun Lou

Publication date: 28 July 2017

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160.2016.1210792

zbMATH Keywords

computational complexitycubic graphmaximum flowcyclic vertex connectivity

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (7)

The \(k\)-subconnectedness of planar graphs ⋮ A Brief Account on the Development and Future Research Directions of Connectivity Properties of Interconnection Networks ⋮ A polynomial algorithm determining cyclic vertex connectivity of \(k\)-regular graphs with fixed \(k\) ⋮ A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs ⋮ Cyclic Vertex (Edge) Connectivity of Burnt Pancake Graphs ⋮ The cubic graphs with finite cyclic vertex connectivity larger than girth ⋮ Characterization of \(k\)-subconnected graphs

Cites Work

• Unnamed Item
• On several sorts of connectivity
• Edge reductions in cyclically \(k\)-connected cubic graphs
• Graph Algorithms
• On computing the connectivities of graphs and digraphs
• Finding the Vertex Connectivity of Graphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Network Flow and Testing Graph Connectivity

This page was built for publication: A polynomial time algorithm for cyclic vertex connectivity of cubic graphs