A note on the rainbow cycle cover problem

作者：Moreno Jorge^*; Martins Simone; Frota Yuri

来源：Networks, 2019, 73(1): 38-47.

DOI：10.1002/net.21833

• branch-and-cut
• edge-colored graph
• graph theory
• integer programming
• preprocessing
• rainbow cycle

Given an edge-colored graph G, a cycle with all its edges with different colors is called a rainbow cycle. The rainbow cycle cover (RCC) problem consists of finding the minimum number of disjoint rainbow cycles covering G. We present an integer linear programming model for the RCC problem and a reduction process for decreasing the dimensions of the graph, resulting in a more efficient method that was able to find new optimal solutions for instances that were unsolved.

• 出版日期2019-1