Պատ․ խմբ.՝ Վ. Հ․ Համբարձումյան (1944-1959) ; Մ․ Մ․ Ջրբաշյան (1960-1965) ; Ա․ Գ․ Նազարով (1966-1983) ; Պատ․ խմբ․ տեղակալ՝ Վ․ Հ․ Ղազարյան (1983-1986) ; Պատ․ խմբ․՝ Դ․ Մ․ Սեդրակյան (1987-1999) ; Գլխավոր խմբ․՝ Ս․ Ա․ Համբարձումյան (2000-2004) ; Վ․ Ս․ Զաքարյան (2005-2018) ; Ռ․ Մ․ Մարտիրոսյան (2018-)

Computer software ; Mathematics ; Science

hypergraph degree sequence ; (0 ; 1)-matrices ; approximation algorithms ; greedy algorithm

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. In this paper we achieve the performance assessment of that algorithm applying the random set cover technique.Տրված աստիճանային հաջորդականությամբ պարզ հիպերգրաֆի գոյության անհրաժեշտ և բավարար պայմաններ գտնելու խնդիրը գրաֆների տեսության հայտնի բաց խնդիրներից մեկն է: Խնդիրը ունի իր մեկնաբանումը բինար մատրիցների տերմիններով: Ներկա աշխատանքում տրվում է այդ ալգորիթմի աշխատանքի գնահատականը՝ բազմությունների ծածկույթի մեթոդի կիրառմամբ: Задача нахождения необходимых и достаточных условий существования простого гиперграфа по данной последовательности степеней вершин является известной открытой задачей теории графов. Задача имеет простую интерпретацию в терминах бинарных матриц. В данной статье приводится оценка работы аппроксимационного алгоритма путем привлечения метода покрытия множеств.

Երևան

ՀՀ ԳԱԱ հրատ.

2017-03-31

Հոդված

Հրապարակման մանրամասներ:

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

Հրապարակման ամսաթիվ:

Հատոր:

Համար:

ISSN:

Պաշտոնական URL:

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

Վերնագիր:

Այլ վերնագիր:

Ստեղծողը:

Աջակից(ներ):

Խորագիր:

Չվերահսկվող բանալի բառեր:

Ծածկույթ:

Ամփոփում:

Հրատարակության վայրը:

Հրատարակիչ:

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

Տեսակ:

Ձևաչափ:

Դասիչ:

Թվայնացում:

Բնօրինակի գտնվելու վայրը: