2 citations · 9 across the 13 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.FL2016★ 2 cited
Approximating the Maximum Number of Synchronizing States in Automata
Andrew Ryzhikov
We consider the problem {\sc Max Sync Set} of finding a maximum synchronizing set of states in a given automaton. We show that the decision version of this problem is PSPACE-comple…
cs.DM2016★ 2 cited
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…