Yüceoğlu, Birol and Şahin, Güvenç (2019) A branch-and-price algorithm for the rainbow cycle cover problems. Networks, 74 (1). pp. 3-15. ISSN 0028-3045 (Print) 1097-0037 (Online)
This is the latest version of this item.
Official URL: http://dx.doi.org/10.1002/net.21869
Abstract
A rainbow cycle in an undirected edge-colored graph is a cycle in which all edges have different colors. A rainbow cycle cover of a graph is a set of disjoint rainbow cycles, where each vertex belongs to exactly one cycle. The objective of the rainbow cycle cover problem is to minimize the number of rainbow cycles used to cover the vertices of the graph while the trivial cycle version also keeps the number of isolated vertices (called trivial rainbow cycles) at minimum. We present a branch-and-price procedure with column generation to solve both versions of the rainbow cycle cover problem. We compare our results with the literature in terms of computational performance. We also discuss two approaches to possibly improve the performance of the branch-and-price procedure.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | branch-and-price; column generation; edge coloring; graph coloring; rainbow cycle; set partitioning |
| Subjects: | T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis |
| Divisions: | Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering Faculty of Engineering and Natural Sciences |
| Depositing User: | Güvenç Şahin |
| Date Deposited: | 05 Aug 2019 22:32 |
| Last Modified: | 17 Jul 2023 21:30 |
| URI: | https://research.sabanciuniv.edu/id/eprint/37780 |
Available Versions of this Item
-
A branch-and-price algorithm for the rainbow cycle cover problems. (deposited 17 Aug 2018 09:50)
- A branch-and-price algorithm for the rainbow cycle cover problems. (deposited 05 Aug 2019 22:32) [Currently Displayed]
Actions (login required)
- View Item