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

Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X 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

Preview

PDF - Accepted Post-Print Version Download (815kB) | Preview

Abstract

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:	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
URI:	https://orca.cardiff.ac.uk/id/eprint/135152

Actions (repository staff only)

Edit Item