RT - article
SR - Electronic
T1 - АЛГОРИТМИЧЕСКИЕ СВОЙСТВА СВЯЗНЫХ ОКРЕСТНОСТНЫХ МНОЖЕСТВ В ГРАФАХ
JF - Известия Национальной академии наук Беларуси. Серия физико-математических наук
SP - 2016-11-21
A1 - КАРТЫННИК Ю. А., 
YR - 2016
UL - https://www.academjournals.by/publication/13052
AB - В работе вводится и характеризуется класс графов, в которых каждое связное доминирующее множество является (связным) окрестностным, а также класс графов, для каждого связного порожденного подграфа которых мощности наименьшего окрестностного множества и наименьшего связного окрестностного множества совпадают. В предположении P ≠ NP доказана неаппроксимируемость за полиномиальное время с логарифмической гарантированной оценкой точности задачи о наименьшем связном окрестностном множестве в их общем подклассе – классе симплициально-расщепляемых графов.