Logo BSU

Please use this identifier to cite or link to this item: http://elib.bsu.by/handle/123456789/6176
Title: Алгоритм распознавания r-мино
Authors: Крылов, Е. В.
Перез Чернов, Александр Хуанович
Keywords: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
Issue Date: Jan-2008
Publisher: БГУ
Citation: Вестник Белорусского государственного университета. Сер. 1, Физика. Математика. Информатика. - 2008. - N 1. - С. 98-101.
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).
URI: http://elib.bsu.by/handle/123456789/6176
ISSN: 0321-0367
Appears in Collections:2008, №1 (январь)

Files in This Item:
File Description SizeFormat 
pages 98-101 from Вестник_БГУ_Январь_2008_Серия1_№1.pdf352,25 kBAdobe PDFView/Open


PlumX

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.