An Efficient Algorithm for Cyclic Edge Connectivity of Regular Graphs

Abstract

In this paper, we develop a polynomial time algorithm to determine the cyclic edge connectivity of a \(k\)-regular graph for \(k \geq 3\). The time complexity of the algorithm is bounded by \(O(k^{11}|V|^8)\), in particular, it is \(O(|V|^8)\) for cubic graphs.