Name
Abstract | ||
|---|---|---|
AbstractWe model and solve the Rainbow Cycle Cover Problem RCCP. Given a connected and undirected graph G=V,E,L and a coloring function ï ź 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. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 684, 260-270 2016 |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1002/net.21700 | Periodicals |
Keywords | Field | DocType |
rainbow cycle cover problem,edge-colored graph,rainbow cycles,branch-and-cut | Integer,Graph,Discrete mathematics,Cycle cover,Combinatorics,Disjoint sets,Branch and cut,Linear programming,Rainbow,Mathematics | Journal |
Volume | Issue | ISSN |
68 | 4 | 0028-3045 |
Citations | PageRank | References |
3 | 0.45 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Selene Silvestri | 1 | 6 | 0.86 |
| Gilbert Laporte | 2 | 8666 | 612.13 |
| R. Cerulli | 3 | 252 | 23.85 |