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

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

Ծածկույթ:

67-78

Ամփոփում:

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

Հրատարակիչ:

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

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

2000-06-18

Ձևաչափ:

pdf

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

oai:arar.sci.am:112300

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

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

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

2000

Հատոր:

vol. 35

Համար:

№ 3

ISSN:

00002-3043

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

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