A polynomial time algorithm for cyclic vertex connectivity of cubic graphs

DOI10.1080/00207160.2016.1210792MaRDI QIDQ4976338zbMATH OpenOpenAlexFDO

Authors Jun Liang, Dingjun Lou, Zan-Bo Zhang

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

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

Recommendations

• 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
• An efficient algorithm for cyclic edge connectivity of regular graphs.
• Algorithm Theory - SWAT 2004
• A polynomial algorithm for cyclic edge connectivity of cubic graphs

Cites work

• Edge reductions in cyclically \(k\)-connected cubic graphs
• Finding the Vertex Connectivity of Graphs
• Graph algorithms. Edited by Guy Even. With a foreword by Richard M. Karp
• Graph theory with applications
• Network Flow and Testing Graph Connectivity
• On computing the connectivities of graphs and digraphs
• On several sorts of connectivity
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(13)

• The \(k\)-subconnectedness of planar graphs
• The cubic graphs with finite cyclic vertex connectivity larger than girth
• Cyclic Vertex (Edge) Connectivity of Burnt Pancake Graphs
• A polynomial algorithm for cyclic edge connectivity of cubic graphs
• A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs
• An improved algorithm for cyclic edge connectivity of regular graphs.
• A brief account on the development and future research directions of connectivity properties of interconnection networks
• Characterization of \(k\)-subconnected graphs
• A polynomial algorithm determining cyclic vertex connectivity of \(k\)-regular graphs with fixed \(k\)
• Cyclic edge and cyclic vertex connectivity of \((4, 5, 6)\)-fullerene graphs
• Algorithm Theory - SWAT 2004
• Cyclic vertex connectivity of minimal circulant graphs
• A cubic algorithm for the directed Eulerian subgraph problem

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

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