Technical Report CS-2012-01

Title: On the Complexity of Constructing Minimum Reload Cost Path-Trees
Authors: Didem Gözüpek and Mordechai Shalom and Ariella Voloshin and Shmuel Zaks
Abstract: The reload cost concept refers to the cost that occurs at a vertex along a path on an edge-colored graph when it traverses an internal vertex between two edges of different colors. The reload cost depends only on the colors of the traversed edges. Previous work on reload costs focuses on the problem of finding a spanning tree that minimizes the total reload cost from a source vertex to all other vertices in a directed graph and proves that this problem is not approximable within any polynomial time computable function of the input size. In this paper we study the complexity and approximability properties of numerous special cases of this problem. We consider both directed and undirected graphs, bounded and unbounded number of colors, bounded and unbounded degree graphs, and bounded and unbounded inter-color reload costs. This problem occurs in various applications such as transportation networks, energy distribution networks, and telecommunications.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2012
To the main CS technical reports page

Computer science department, Technion