Thumbnail

The Minimum Reload s-t Path/Trail/Walk Problems

Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2009), The Minimum Reload s-t Path/Trail/Walk Problems, in Nielsen, Mogens; Kucera, Antonin; Miltersen, Peter Bro; Palamidessi, Catuscia; Tuma, Petr; Valencia, Frank, SOFSEM 2009: Theory and Practice of Computer Science 35th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 24-30, 2009. Proceedings, Springer : Berlin, p. 621-632. http://dx.doi.org/10.1007/978-3-540-95891-8_55

View/Open
Type
Communication / Conférence
Date
2009
Conference title
35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2009)
Conference date
2009-01
Conference city
Spindleruv Mlyn
Conference country
République tchèque
Book title
SOFSEM 2009: Theory and Practice of Computer Science 35th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 24-30, 2009. Proceedings
Book author
Nielsen, Mogens; Kucera, Antonin; Miltersen, Peter Bro; Palamidessi, Catuscia; Tuma, Petr; Valencia, Frank
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
5404
Published in
Berlin
ISBN
978-3-540-95890-1
Pages
621-632
Publication identifier
Metadata
Show full item record
Author(s)
Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lyra, Adria

Martinhon, Carlos A.

Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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.
Subjects / Keywords
non-oriented edge-colored graphs