Abstract:

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.
; Задача нахождения необходимых и достаточных условий существования простого гиперграфа по данной последовательности степеней вершин является известной открытой задачей теории графов. Задача имеет простую интерпретацию в терминах бинарных матриц. В предыдущих работах были исследованы задачи существования и построения бинарных матриц с данными ограничениями и построен аппроксимационный алгоритм. В данной статье приводится оценка работы аппроксимационного алгоритма путем привлечения метода покрытия множеств.

Date created:

2017

Identifier:

oai:noad.sci.am:135843

ISSN:

0321-1339

Other identifier:

UDC 119

Language:

English

Journal or Publication Title:

Reports of NAS RA

Volume:

117

Number:

1

URL:

Additional Information:

hsahakyan@sci.am

Affiliation:

Institute for Informatics and Automation Problems

Country:

Armenia

Indexing:

ASCI