2 citations · 9 across the 13 of their papers we have counts for
4 papers · 1 filter
Careful synchronisation and the diameter of transformation semigroups with few generators
Andrew Ryzhikov
A word is called carefully synchronising for a partial deterministic finite semi-automaton if it maps all states to the same state. Equivalently, it is a composition of partial tra…
The complexity of computing the period and the exponent of a digraph
Stefan Kiefer, Andrew Ryzhikov
The period of a strongly connected digraph is the greatest common divisor of the lengths of all its cycles. The period of a digraph is the least common multiple of the periods of i…
On shortest products for nonnegative matrix mortality
Andrew Ryzhikov
Given a finite set of matrices with integer entries, the matrix mortality problem asks if there exists a product of these matrices equal to the zero matrix. We consider a special c…
On Minimum Maximal Distance-k Matchings
Yury Kartynnik, Andrew Ryzhikov
We study the computational complexity of several problems connected with finding a maximal distance- matching of minimum cardinality or minimum weight in a given graph. We intro…