On the complexity of traversing labyrinths by an automaton

The class of all finite labyrinths with finite holes with diameter no larger than a given natural number $n$ was considered by S. A. Bogomolov, A. A. Zolotykh and A. N. Zyrychev [Avtomaty i grafy (Automata and graphs), Saratov. Univ., Saratov, 1991; per bibl.]. They showed that a universal shunt having no more than $Cn^2$ states exists for this class. In this paper we give a more efficient bypass algorithm than the one in the above-cited book. We construct a universal shunt for this class that has $Cn$ states.