The minimum reload image–image path, trail and walk problems Original Research Article

This paper deals with problems on non-oriented edge-colored graphs. The aim is to find a route between two given vertices image and image. This route can be a walk, a trail or a path. Each time a vertex is crossed by a walk there is an associated non-negative reload cost image, where image and image denote, respectively, the colors of successive edges in this walk. The goal is to find a route whose total reload cost is minimum. Polynomial algorithms and proofs of NP-hardness are given for particular cases: when the triangle inequality is satisfied or not, when reload costs are symmetric (i.e., image) or asymmetric. We also investigate bounded degree graphs and planar graphs. We conclude the paper with the traveling salesman problem with reload costs.