The Rainbow Cycle Cover Problem

Selene Silvestri, Gilbert Laporte, Raffaele Cerulli

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

We model and solve the Rainbow Cycle Cover Problem (RCCP). Given a connected and undirected graph G = (V,E,L) and a coloring function l that assigns a color to each edge of G from the finite color set L, 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 G. 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.

Original languageEnglish
Pages (from-to)260-270
Number of pages11
JournalNetworks
Volume68
Issue number4
DOIs
Publication statusPublished - 1 Dec 2016

Keywords

  • branch-and-cut
  • edge-colored graph
  • rainbow cycle cover problem
  • rainbow cycles

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'The Rainbow Cycle Cover Problem'. Together they form a unique fingerprint.

Cite this