Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

The path contraction algorithm for the problem of finding a simple path of a given length

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
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover