The minimum reload s–t path, trail and walk problems
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2010), The minimum reload s–t path, trail and walk problems, Discrete Applied Mathematics, 158, 13, p. 1404-1417. http://dx.doi.org/10.1016/j.dam.2010.03.009
Type
Article accepté pour publication ou publiéDate
2010Journal name
Discrete Applied MathematicsVolume
158Number
13Publisher
Elsevier
Pages
1404-1417
Publication identifier
Metadata
Show full item recordAuthor(s)
Gourvès, LaurentLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lyra, Adria
Martinhon, Carlos A.
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
This paper deals with previous termproblemsnext term on non-oriented edge-colored graphs. The aim is to find a route between two given vertices previous terms and t. This route can be a previous termwalk,next term a previous termtrailnext term or a previous termpath.next term Each time a vertex is crossed by a previous termwalknext term there is an associated non-negative previous termreloadnext term cost ri,j, where i and j denote, respectively, the colors of successive edges in this previous termwalk.next term The goal is to find a route whose total previous termreloadnext term cost is previous termminimum.next term Polynomial algorithms and proofs of NP-hardness are given for particular cases: when the triangle inequality is satisfied or not, when previous termreloadnext term costs are symmetric (i.e., ri,j=rj,i) or asymmetric. We also investigate bounded degree graphs and planar graphs. We conclude the paper with the traveling salesman previous termproblem with reloadnext term costs.Subjects / Keywords
Edge-colored graphs; NP-hardness; Paths, trails and walks; TSP; Inapproximability; Reload optimizationRelated items
Showing items related by title and author.
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2009) Communication / Conférence
-
Gourvès, Laurent; Martinhon, Carlos A.; Monnot, Jérôme; Adria, Lyra; Protti, Fabio (2009) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2012) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2013) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2010) Communication / Conférence