On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs

Babak Ghanbari, Robert Šámal

We present an algorithm for finding a perfect matching in a $3$-edge-connected cubic graph that intersects every $3$-edge cut in exactly one edge. Specifically, we propose an algor…