Abstract:

Տրված աստիճանային հաջորդականությամբ պարզ հիպերգրաֆի գոյության անհրաժեշտ և բավարար պայմաններ գտնելու խնդիրը գրաֆների տեսության հայտնի բաց խնդիրներից մեկն է: Խնդիրը ունի իր մեկնաբանումը բինար մատրիցների տերմիններով: Նախորդող աշխատանքներում հետազոտվել են տրված սահմանափակումներով մատրիցների գոյության / կառուցման հարցերը և կառուցվել է ապրոքսիմացիոն ալգորիթմ: Ներկա աշխատանքում տրվում է այդ ալգորիթմի աշխատանքի գնահատականը՝ բազմությունների ծածկույթի մեթոդի կիրառմամբ:
; Задача нахождения необходимых и достаточных условий существования простого гиперграфа по данной последовательности степеней вершин является известной открытой задачей теории графов. Задача имеет простую интерпретацию в терминах бинарных матриц. В предыдущих работах были исследованы задачи существования и построения бинарных матриц с данными ограничениями и построен аппроксимационный алгоритм. В данной статье приводится оценка работы аппроксимационного алгоритма путем привлечения метода покрытия множеств.

Identifier:

oai:noad.sci.am:135843

Language:

Անգլերեն

Journal or Publication Title:

ՀՀ ԳԱԱ Զեկույցներ

Affiliation:

Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ

Country:

Հայաստան