×

The minimum reload \(s-t\) path, trail and walk problems. (English) Zbl 1209.05131

Summary: This paper deals with problems on non-oriented edge-colored graphs. The aim is to find a route between two given vertices \(s\) and \(t\). 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 \(r_{i,j}\), where \(i\) and \(j\) 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., \(r_{i,j}=r_{j,i}\)) or asymmetric. We also investigate bounded degree graphs and planar graphs. We conclude the paper with the traveling salesman problem with reload costs.

MSC:

05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abouelaoualim, A.; Das, K. C.; Faria, L.; Manoussakis, Y.; Martinhon, C. A.; Saad, R., Paths and trails in edge-colored graphs, Theoretical Computer Science, 409, 3, 497-510 (2008) · Zbl 1155.68053
[2] E. Amaldi, G. Galbiati, F. Maffioli, On minimum reload cost paths, tours and flows, in: Proc. of the Cologne Twente Workshop, CTW 2008, 2008.; E. Amaldi, G. Galbiati, F. Maffioli, On minimum reload cost paths, tours and flows, in: Proc. of the Cologne Twente Workshop, CTW 2008, 2008. · Zbl 1219.68121
[3] Berman, P.; Karpinski, M.; Scott, A. D., (Approximation Hardness of Short Symmetric Instances of MAX-3SAT. Approximation Hardness of Short Symmetric Instances of MAX-3SAT, Electronic Colloquium on Computational Complexity (ECCC), vol. 49 (2003))
[4] Galbiati, G., The complexity of a minimum reload cost diameter problem, Discrete Applied Mathematics, 156, 3494-3497 (2008) · Zbl 1168.68035
[5] I. Gamvros, Satellite network design, optimization and management, Ph.D. Thesis, University of Maryland, 2006.; I. Gamvros, Satellite network design, optimization and management, Ph.D. Thesis, University of Maryland, 2006.
[6] I. Gamvros, L. Gouveia, S. Raghavan, Reload cost trees and network design, in: Proc. of the International Network Optimization Conference, INOC 2007, 2007.; I. Gamvros, L. Gouveia, S. Raghavan, Reload cost trees and network design, in: Proc. of the International Network Optimization Conference, INOC 2007, 2007. · Zbl 1248.68379
[7] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039
[8] Gerards, A. M.H., Matching: Network Models (1995), North Holland: North Holland Amsterdam · Zbl 0839.90131
[9] Wirth, H. C.; Steffan, J., Reload cost problems: minimum diameter spanning tree, Discrete Applied Mathematics, 113, 73-85 (2001) · Zbl 1003.05061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.