@article{КАРТЫННИК Ю. А.2016-11-21,
author = { КАРТЫННИК Ю. А.},
title = {АЛГОРИТМИЧЕСКИЕ СВОЙСТВА СВЯЗНЫХ ОКРЕСТНОСТНЫХ МНОЖЕСТВ В ГРАФАХ},
year = {2016},
publisher = {NP «NEICON»},
abstract = {В работе вводится и характеризуется класс графов, в которых каждое связное доминирующее множество является (связным) окрестностным, а также класс графов, для каждого связного порожденного подграфа которых мощности наименьшего окрестностного множества и наименьшего связного окрестностного множества совпадают. В предположении P ≠ NP доказана неаппроксимируемость за полиномиальное время с логарифмической гарантированной оценкой точности задачи о наименьшем связном окрестностном множестве в их общем подклассе – классе симплициально-расщепляемых графов.},
URL = {https://www.academjournals.by/publication/13052},
eprint = {https://www.academjournals.by/files/13018},
journal = {Известия Национальной академии наук Беларуси. Серия физико-математических наук},
}