A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges

Katarzyna Paluch, Mateusz Wasylkiewicz

We consider three variants of the problem of finding a maximum weight restricted $2$-matching in a subcubic graph $G$. (A $2$-matching is any subset of the edges such that each ver…