Publication Details:

«ՀՀ ԳԱԱ Տեղեկագիր: Մաթեմատիկա»-ն լույս է տեսնում 1966 թվականից՝ տարին 6 անգամ։

Journal or Publication Title:

ՀՀ ԳԱԱ Տեղեկագիր: Մաթեմատիկա =Известия НАН Армении: Математика =Proceedings of the NAS Armenia: Mathematics

Date of publication:

2000

Volume:

35

Number:

3

ISSN:

00002-3043

Official URL:

Additional Information:

click here to follow the link

Other title:

On some algorithms and properties of comparability draphs / S. E. Markosyan.

Contributor(s):

Գլխավոր խմբ․՝ Մ․ Մ․ Ջրբաշյան (1966-1994) ; Ռ․ Վ․ Համբարձումյան (1994-2009) ; Ա․ Ա․ Սահակյան (2010-)

Coverage:

67-78

Abstract:

Если граф и его дополнение являются графами сравнения, то при любой транзитивной ориентации этих графов существуют вершины minimin, minmax и maxmax (minmin-вершина, которая min в графе и в его дополнении, minmax,- вершина, которая min в графе и max в его дополнении, и т.д. ,). Из этого свойства следует теорема Пнуели, Лемпела и Эвена о графах подстановок. Разработаны алгоритмы решения для таких задач как нахождение максимального числа попарно непересекающихся максимальных независимых множеств и наибольшего q-хроматического подграфа.

Place of publishing:

Երևան

Publisher:

Հայաստանի ԳԱԱ

Date created:

2000-06-18

Format:

pdf

Identifier:

oai:arar.sci.am:112300

Call number:

АЖ 411

Digitization:

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

Location of original object:

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