کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420297 | 683920 | 2010 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The minimum reload ss–tt path, trail and walk problems The minimum reload ss–tt path, trail and walk problems](/preview/png/420297.png)
This paper deals with problems on non-oriented edge-colored graphs. The aim is to find a route between two given vertices ss and tt. 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 ri,jri,j, where ii and jj 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., ri,j=rj,iri,j=rj,i) or asymmetric. We also investigate bounded degree graphs and planar graphs. We conclude the paper with the traveling salesman problem with reload costs.
Journal: Discrete Applied Mathematics - Volume 158, Issue 13, 6 July 2010, Pages 1404–1417