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

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.

[thumbnail of final_version.pdf]
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: Completion
Status: Unpublished
Schools: Mathematics
Related URLs:
Date of First Compliant Deposit: 25 April 2024
Last Modified: 20 May 2024 11:08
URI: https://orca.cardiff.ac.uk/id/eprint/168355

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics