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

"ՀՀ ԳԱԱ Զեկույցներ" հանդեսը հիմնադրվել է 1944թ.: Լույս է տեսնում տարին 4 անգամ:

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

ՀՀ ԳԱԱ Զեկույցներ = Доклады НАН РА = Reports NAS RA

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

2013

Հատոր:

113

Համար:

1

ISSN:

0321-1339

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

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

սեղմիր այստեղ կապին հետևելու համար

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

Երկկողմանի գրաֆի բոլոր մաքսիմալ անկախ բազմությունների բազմության մասին / Վ. Գ. Մինասյան։ О множестве всех максимальных независимых множеств двудольного графа / В. Минасян.

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

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

Ծածկույթ:

37-47

Ամփոփում:

It is shown that the set of all maximum independent sets of bipartite graph is a distributive lattice, which allows to view the problem of generating the maximum independent sets of bipartite graph in a new aspect, namely, to find not all, but only the join-irreducible maximum independent sets. Also an algorithm providing these sets is presented, the complexity of which doesn’t exceed the complexity of the best algorithm providing just one maximum independent set. Ցույց է տրվում, որ երկկողմանի գրաֆի մաքսիմալ անկախ բազմությունների բազմությունը բաշխական կավար է, ինչը թույլ է տալիս երկկողմանի գրաֆի մաքսիմալ անկախ բազմությունների գեներացման խնդիրը դիտել որոշակիորեն նոր 47 ասպեկտում, այն է՝ գտնել ոչ թե բոլոր, այլ միայն միավորմամբ անբաղադրելի մաքսիմալ անկախ բազմությունները։ Նաև ներկայացվում է այդ բազմությունները տրամադրող ալգորիթմ, որի բարդությունը ավելին չէ, քան միայն մեկ մաքսիմալ անկախ բազմություն տրամադրող լավագույն ալգորիթմի բարդությունը։ Показано, что множество всех максимальных независимых множеств двудольного графа есть дистрибутивная решетка, что позволяет рассматривать задачу генерации максимальных независимых множеств двудольного графа в некотором новом аспекте, а именно, найти не все, а только неразложимые в объединение максимальные независимые множества. Также приведен алгоритм, предоставляющий эти множества, сложность которого не больше сложности наилучшего алгоритма, предоставляющего только одно максимальное независимое множество.

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

Երևան

Հրատարակիչ:

ՀՀ ԳԱԱ հրատ.

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

2013-03-20

Ձևաչափ:

pdf

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

oai:arar.sci.am:46568

Դասիչ:

АЖ 144

Թվայնացում:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան

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

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան