Applied Graph Theory

Finding a family of simple circuits in graphs with vertex semidegrees bounded by $k$

A. A. Medvedev

Bauman Moscow State Technical University, Moscow, Russia

Abstract: We study the algorithmic complexity of finding a family of simple circuits passing every vertice of a digraph with semidegree bounded by $k$. The problem is considered in two variants: as a search and as an optimization problem. Parametrically polynomial solvability of the problem is proved in both variants, Algorithms with complexity $O(nk^2 + n\log_{2}n)$, $O(n(k^2 + k) + n\log_{2}n)$ and $O(n)$ for various types of constraints are proposed, where $n$ is the number of digraph vertices.

Keywords: digraphs, simple circuits, search problems, optimization, P class, parametrical complexity, polynomial solvability.

UDC: 519.176

DOI: 10.17223/20710410/60/7