The path contraction algorithm for the problem of finding a simple path of a given length
Received: 09 Nov 2026 Revised: 10 Nov 2026 Accepted: 10 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 156–159
Abstract
The paper considers the problem of finding a simple path of a given length between specified vertices in a connected undirected weighted graph without multiple edges and loops, all edge weights of which are positive numbers. This problem arises when planning transport routes with guaranteed delay or when analyzing graphs that arise in microbiology. The authors propose a new algorithm for solving the problem of finding a simple path of a given length in a graph. The developed algorithm is based on the gradual transformation of the graph and the elimination of simple paths that cannot be part of the sought‑after simple path. The paper presents estimates of the time and space complexity of the new algorithm in the average and worst cases, and also presents the results of numerical experiments comparing this algorithm with the modified Yen’s algorithm.
Keywords: Yen’s algorithm, simple path search, Erdős–Rényi random graph.
BibTeX
@article{IS-Vaschenko-Mastikhina2026,
author = {Vaschenko, Maksim Igorevich and Mastikhina, Anna Antonovna},
title = {{The path contraction algorithm for the problem of finding a simple path of a given length}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {156--159},
}
AMSBIB
\Bibitem{IS-Vaschenko-Mastikhina2026}
\by M.\,I.~Vaschenko, A.\,A.~Mastikhina
\paper The path contraction algorithm for the problem of finding a simple path of a given length
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 156--159
\lang In Russian
RU