Networks

Minimum reload cost cycle cover in complete graphs

Journal Article

Abstract The reload cost refers to the cost that occurs along a path on an edge‐colored graph when it traverses an internal vertex between two edges of different colors. Galbiati et al. introduced the Minimum Reload Cost Cycle Cover problem, which is to find a set of vertex‐disjoint cycles spanning all vertices with minimum reload cost. They proved that this problem is strongly NP‐hard and not approximable within 1/ϵ for any ϵ > 0 even when the number of colors is 2, the reload costs are symmetric and satisfy the triangle inequality. In this paper, we prove that the minimum reload cost is zero on complete graphs with n vertices and 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. This algorithm also finds a monochromatic cycle cover in complete graphs with a nearly equitable 2‐edge‐coloring except for some special cases.

Related Topics

Related Publications

Related Content

Site Footer

Address:

This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.