Article ID: | iaor20062928 |
Country: | Canada |
Volume: | 1 |
Issue: | 1 |
Start Page Number: | 31 |
End Page Number: | 45 |
Publication Date: | Jan 2006 |
Journal: | Algorithmic Operations Research |
Authors: | Forlizzi Luca, Hromkovi Juraj, Proietti Guido, Seibert Sebastian. |
Keywords: | graphs |
We consider the problem of finding a cheapest Hamiltonian path of a complete graph satisfying a relaxed triangle inequality, i.e., such that for some parameter β > 1, the edge costs satisfy the inequality