Efficient Generation of One-Factorizations through Hill Climbing

Maya Dotan, Nati Linial

It is well known that for every even integer $n$, the complete graph $K_n$ has a one-factorization, namely a proper edge coloring with $n-1$ colors. Unfortunately, not much is kn…