Skip to Main content Skip to Navigation
Conference papers

Minimum Reload Cost Graph Factors

Abstract : 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.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02342817
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, January 17, 2020 - 2:29:40 PM
Last modification on : Monday, January 27, 2020 - 1:51:08 PM

File

1810.11700.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

72

Files downloads

75