О некоторых алгоритмах и свойствах графов сравнения - С. Е. Маркосян (Հայաստանի ԳԱԱ)
Если граф и его дополнение являются графами сравнения, то при любой транзитивной ориентации этих графов существуют вершины minimin, minmax и maxmax (minmin-вершина, которая min в графе и в его дополнении, minmax,- вершина, которая min в графе и max в его дополнении, и т.д. ,). Из этого свойства следует теорема Пнуели, Лемпела и Эвена о графах подстановок. Разработаны алгоритмы решения для таких задач как нахождение максимального числа попарно непересекающихся максимальных независимых множеств и наибольшего q-хроматического подграфа.
Keywords: Mathematics; Science