On some algorithms and properties of comparability draphs / S. E. Markosyan.
Если граф и его дополнение являются графами сравнения, то при любой транзитивной ориентации этих графов существуют вершины minimin, minmax и maxmax (minmin-вершина, которая min в графе и в его дополнении, minmax,- вершина, которая min в графе и max в его дополнении, и т.д. ,). Из этого свойства следует теорема Пнуели, Лемпела и Эвена о графах подстановок. Разработаны алгоритмы решения для таких задач как нахождение максимального числа попарно непересекающихся максимальных независимых множеств и наибольшего q-хроматического подграфа.
oai:arar.sci.am:112300
ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան
Jul 20, 2020
Apr 2, 2020
0
https://arar.sci.am/publication/123593
Հրատարակության անուն | Ամսաթիվ |
---|---|
О некоторых алгоритмах и свойствах графов сравнения | Jul 20, 2020 |
E. P. Serrano M. I. Troparevsky M. A. Fabio