Ամփոփում:

Necessary and sufficient conditions for the existence of a simple hypergraph with the given degree sequence is one of the known open problems in the graph theory domain. The problem has its interpretation in terms of binary matrices. Existence/construction issues of related matrices with the given parameters/constraints were investigated and an approximation algorithm is constructed in earlier works. In this paper we achieve the performance assessment of that algorithm applying the random set cover technique.
; Задача нахождения необходимых и достаточных условий существования простого гиперграфа по данной последовательности степеней вершин является известной открытой задачей теории графов. Задача имеет простую интерпретацию в терминах бинарных матриц. В предыдущих работах были исследованы задачи существования и построения бинарных матриц с данными ограничениями и построен аппроксимационный алгоритм. В данной статье приводится оценка работы аппроксимационного алгоритма путем привлечения метода покрытия множеств.

Ստեղծման ամսաթիվը:

2017

Նույնականացուցիչ:

oai:noad.sci.am:135843

ISSN:

0321-1339

Այլ նույնացուցիչ:

UDC 119

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Reports of NAS RA

Հատոր:

117

Համար:

1

URL:

լրացուցիչ տեղեկատվություն:

hsahakyan@sci.am

Կազմակերպության անվանում:

Institute for Informatics and Automation Problems

Երկիր:

Armenia

Ինդեքսավորում:

ASCI