The Rainbow Cycle Cover Problem
S. De Silvestri, Gilbert Laporte, Raffaele Cerulli · Networks · 2016
We model and solve the Rainbow Cycle Cover Problem (RCCP). Given a connected and undirected graph and a coloring function that assigns a color to each edge of from the finite color set , a cycle whose edges have all different colors is called a rainbow cycle. The RCCP consists of finding the minimum number of disjoint rainbow cycles covering . The RCCP on general graphs is known to be NP‐complete. We model the RCCP as an integer linear program, we derive valid inequalities and we solve it by branch‐and‐cut. Computational results are reported on randomly generated instances. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(4), 260–270 2016