Minimum Reload Cost Graph Factors - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

Minimum Reload Cost Graph Factors


The concept of Reload cost in a graph refers to the cost that occurs while traversing a vertex via two of its incident edges. This cost is uniquely determined by the colors of the two edges. This concept has various applications in transportation networks, communication networks, and energy distribution networks. Various problems using this model are defined and studied in the literature. The problem of finding a spanning tree whose diameter with respect to the reload costs is the smallest possible, the problems of finding a path, trail or walk with minimum total reload cost between two given vertices, problems about finding a proper edge coloring of a graph such that the total reload cost is minimized, the problem of finding a spanning tree such that the sum of the reload costs of all paths between all pairs of vertices is minimized, and the problem of finding a set of cycles of minimum reload cost, that cover all the vertices of a graph, are examples of such problems. In this work we focus on the last problem. Noting that a cycle cover of a graph is a 2-factor of it, we generalize the problem to that of finding an r -factor of minimum reload cost of an edge colored graph. We prove several $NP$-hardness results for special cases of the problem. Namely, bounded degree graphs, planar graphs, bounded total cost, and bounded number of distinct costs. For the special case of r =2 , our results imply an improved $NP$-hardness result. On the positive side, we present a polynomial-time solvable special case which provides a tight boundary between the polynomial and hard cases in terms of r and the maximum degree of the graph. We then investigate the parameterized complexity of the problem, prove W[1]-hardness results and present an FPT-algorithm.
Fichier principal
Vignette du fichier
1810.11700.pdf (507.91 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-02342817 , version 1 (17-01-2020)



Julien Baste, Didem Gözüpek, Mordechai Shalom, Dimitrios M. Thilikos. Minimum Reload Cost Graph Factors. SOFSEM, Jan 2019, Nový Smokovec, Slovakia. pp.67-80, ⟨10.1007/978-3-030-10801-4_7⟩. ⟨lirmm-02342817⟩
65 View
109 Download



Gmail Facebook X LinkedIn More