Алгоритм распознавания r-мино
Пусть M r - класс r-мино графов. Известно, что при любом фиксированном r для класса M r существует конечная характеризация в терминах запрещенных индуцированных подграфов. Нами предложен алгоритм, решающий распознавательную задачу «G∈M r», r - фиксировано, за время O(m), где m - число ребер графа G. Также предложен алгоритм, вычисляющий хеллиеву размерность h=hd(G) графа G за время O(h 4m).