Determining fixed-length paths in directed and undirected edge-weighted graphs

Hambly, Daniel, Lewis, Rhydian ORCID: https://orcid.org/0000-0003-1046-811X and Corcoran, Padraig ORCID: https://orcid.org/0000-0001-9731-3385 2024. Determining fixed-length paths in directed and undirected edge-weighted graphs. Presented at: Symposium on Experimental Algorithms (SEA) 2024, Vienna, Austria, 24-26 July 2024. Published in: Liberti, Leo ed. 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs) , vol.301 15.1-15.11. 10.4230/LIPIcs.SEA.2024.15

Preview

PDF - Accepted Post-Print Version Available under License Creative Commons Attribution. Download (769kB) | Preview

Abstract

In this paper, we examine the N P-hard problem of identifying fixed-length s-t paths in edge-weighted graphs – that is, a path of a desired length k from a source vertex s to a target vertex t. Many existing strategies look at paths whose lengths are determined by the number of edges in the path. We, however, look at the length of the path as the sum of the edge weights. Here, three exact algorithms for this problem are proposed: the first based on an integer programming (IP) formulation, the second a backtracking algorithm, and the third based on an extension of Yen’s algorithm. Analysis of these algorithms on random graphs shows that the backtracking algorithm performs best on smaller values of k, whilst the IP is preferable for larger values of k.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Mathematics
ISBN:	9783959773256
Date of First Compliant Deposit:	25 April 2024
Last Modified:	26 Sep 2024 10:53
URI:	https://orca.cardiff.ac.uk/id/eprint/168355

Actions (repository staff only)

Edit Item