Hambly, Daniel, Lewis, Rhyd  ORCID: https://orcid.org/0000-0003-1046-811X and Corcoran, Padraig ORCID: https://orcid.org/0000-0001-9731-3385
2026.
Methods for finding paths of a prescribed length in weighted graphs.
Presented at: EvoCOP 2026,
Toulouse, France,
8-10 April 2026.
Published in: Krejca, Martin S. and Pillay, Nelishia eds.
Evolutionary Computation in Combinatorial Optimization.
Lecture Notes in Computer Science
, vol.16522
Cham:
Springer Nature Switzerland,
pp. 68-84.
10.1007/978-3-032-20537-7_5
|
Preview |
PDF
- Accepted Post-Print Version
Available under License Creative Commons Attribution. Download (572kB) | Preview |
Abstract
This paper tackles the NP-hard problem of finding paths of a prescribed length between a source and a target node in weighted directed and undirected graphs. To address this problem, we propose and analyse two algorithms: a heuristic method based on local search, and an exact backtracking algorithm that utilises several problem-specific operators to improve runtimes. We also present several general methods for reducing problem size. These involve removing nodes that can never be in any path from the source to the target, smoothing nodes that can be replaced with an arc, and removing nodes whose shortest path sum from the source and the target exceeds the prescribed length. Analysis on real-world street networks shows that the local search algorithm achieves solutions within a few metres of the prescribed length and consistently yields lower costs than the backtracking algorithm, even under a more restricted time limit. In contrast, some of our backtracking operators achieve lower-cost solutions on random and dense planar graphs.
| Item Type: | Conference or Workshop Item - published (Paper) |
|---|---|
| Date Type: | Publication |
| Status: | Published |
| Schools: | Schools > Computer Science & Informatics Schools > Mathematics |
| Additional Information: | RRS policy applied |
| Publisher: | Springer Nature Switzerland |
| ISBN: | 9783032205360 |
| ISSN: | 0302-9743 |
| Date of First Compliant Deposit: | 25 March 2026 |
| Last Modified: | 25 Mar 2026 11:45 |
| URI: | https://orca.cardiff.ac.uk/id/eprint/185925 |
Actions (repository staff only)
 |
Edit Item |
Dimensions
Dimensions