An algorithm for cyclic edge connectivity of cubic graphs

The cyclic edge connectivity is the size of a smallest edge cut in a graph such that at least two of the connected components contain cycles. We present an algorithm running in time O(n 2log2 n) for computing the cyclic edge connectivity of n-vertex cubic graphs.