Page 79 - ARAŞTIRMA ÖZETLERİ

LİSANSÜSTÜ ARAŞTIRMALAR SEMPOZYUMU & TANITIM GÜNLERİ 2018

Minimum Reload Cost Cycle Cover in Complete Graphs

Yasemin BÜYÜKÇOLAK, Didem GÖZÜPEK, Sibel ÖZKAN
Matematik ABD

ÖZET
Edge-colored graphs can be used to model various network design problems. We consider an optimization

problem with the reload cost model. The reload cost occurs along a path on an edge-colored graph while traversing
an internal vertex via two consecutive edges of diferent colors. That is, the reload cost depends only on the colors of
the incident traversed edges. The reload cost concept is used in many areas such as transportation networks,
telecommunication networks, and energy distribution networks. For instance, in a cargo transportation network,
each carrier can be represented by a color and the reload costs arise only at points where the carrier changes, i.e.
during transition from one color to another. In telecommunication networks, switching among different technologies
such as cables, fibers, and satellite links or switching between different providers such as different commercial
satellite providers in satellite networks correspond to reload costs. In energy distribution networks, the reload cost
corresponds to the loss of energy while transferring energy from one form to another one, such as the conversion of
natural gas from liquid to gas form.

In the literature, it is proved that the Minimum Reload Cost Cycle Cover problem, which is to find a set of
vertex-disjoint cycles spanning all vertices with minimum reload cost, is strongly NP-hard and not approximable
within 1/ε for any ε > 0. In this study, we focus on this problem in complete graphs having equitable or nearly
equitable 2-edge-colorings. We prove that the minimum reload cost is zero on complete graphs Kn with an equitable
2-edge-coloring except possibly n = 4 or with a nearly equitable 2-edge-coloring except possibly for n ≤ 13.
Furthermore, we provide a polynomial-time algorithm that constructs a monochromatic cycle cover in complete
graphs Kn with an equitable 2-edge-coloring except possibly for n = 4.
Anahtar Kelimeler: Optimization, Network Design, Reload Cost, Minimum Reload Cost Cycle Cover, Complete Graph,
Equitable Edge-Coloring, Nearly Equitable Edge-Coloring, Monochromatic Cycle Cover.

77