This article is cited in 1 paper

Part 3. Mathematical models

Finding a family of simple circuits in a digraph with semidegree bound $ 2 $

A. A. Medvedev

Bauman Moscow State Technical University

Abstract: The present paper investigates the algorithmic complexity of finding a family of simple circuits passing every vertice of a digraph with semidegree bound $ 2 $. The problem is considered in two variants: as a search and as an optimization problem. It proves to be polinomially solvable in both variants, subsequently an algorithm using time $ O(n^3) $ and, for a particular formulation of the problem, an algorithm using time $ O(n^2) $ are suggested where n is the number of the digraph’s vertices.

Keywords: digraphs, simple circuits, search problems, optimization, $P$ class, polynomail solvability.