Object

Title: Hypergraph Degree Sequence Approximation ; Аппроксимация последовательности степенейвершин гиперграфа

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

Object collections:

Last modified:

Mar 3, 2021

In our library since:

Jul 21, 2020

Number of object content hits:

19

All available object's versions:

https://noad.sci.am/publication/149385

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

This page uses 'cookies'. More information