Portal de Periódicos da CAPES

Capítulo de livro Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

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

2009; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-540-95891-8_55

1611-3349

Laurent Gourvès, Adria Lyra, Carlos A. Martinhon, Jérôme Monnot,

Optimization and Packing Problems

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.