Алгоритм распознавания r-мино

Abstract

Graph G=(V,E) is called r-mino, if each vertex v∈V belongs at least to r maximal cliques. The class of r-mino is denoted by Mr. It is known an approach to solve the recognition problem G∈ Mr (r is fixed) in polynomial time. We propose the O(m) (m=|E|) algorithm of r-mino recognition (r is fixed) and the algorithm solving the problem of determining the Helly dimension h=hd(G) of a graph G in O(h4m) time. = Пусть Mr – класс r-мино графов. Известно, что при любом фиксированном r для класса Mr существует конечная характеризация в терминах запрещенных индуцированных подграфов. Нами предложен алгоритм, решающий распознавательную задачу «G∈Mr», r – фиксировано, за время O(m), где m – число ребер графа G. Также предложен алгоритм, вычисляющий хеллиеву размерность h=hd(G) графа G за время O(h4m).