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.
;
Задача нахождения необходимых и достаточных условий существования простого гиперграфа по данной последовательности степеней вершин является известной открытой задачей теории графов. Задача имеет простую интерпретацию в терминах бинарных матриц. В предыдущих работах были исследованы задачи существования и построения бинарных матриц с данными ограничениями и построен аппроксимационный алгоритм. В данной статье приводится оценка работы аппроксимационного алгоритма путем привлечения метода покрытия множеств.
oai:noad.sci.am:135843
Institute for Informatics and Automation Problems
Mar 3, 2021
Jul 21, 2020
19
https://noad.sci.am/publication/149385
Edition name | Date |
---|---|
А. А. Саакян, Аппроксимация последовательности степенейвершин гиперграфа | Mar 3, 2021 |
Aslanyan Levon Ryazanov Vladimir Sahakyan Hasmik
Sahakyan Hasmik Ryazanov Vladimir Margaryan Ani
Sahakyan Hasmik Margaryan Ani
Sahakyan Hasmik Aslanyan Levon