Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

A shortest path algorithm for graphs featuring transfer costs at their vertices

Lewis, Rhyd ORCID: 2020. A shortest path algorithm for graphs featuring transfer costs at their vertices. Presented at: International Conference on Computational Logistics, Enschede, The Netherlands, 28–30 Sept 2020. Computational Logistics. Lecture Notes in Computer Science. , vol.12433 Springer Verlag, pp. 539-552. 10.1007/978-3-030-59747-4_35

[thumbnail of paper.pdf]
PDF - Accepted Post-Print Version
Download (815kB) | Preview


This paper examines the problem of finding shortest paths in graphs that feature additional penalties – transfer costs – at their vertices. We propose a shortest path algorithm that can cope with these additional penalties without the need of first performing a graph expansion, which is the typical algorithmic strategy. While our method exhibits an inferior growth rate compared to existing approaches, we show that it is more efficient on sparse graphs.

Item Type: Conference or Workshop Item (Paper)
Date Type: Publication
Status: Published
Schools: Mathematics
Publisher: Springer Verlag
ISSN: 0302-9743
Date of First Compliant Deposit: 28 September 2020
Date of Acceptance: 30 July 2020
Last Modified: 07 Nov 2022 11:17

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics