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.