АЛГОРИТМИЧЕСКИЕ СВОЙСТВА СВЯЗНЫХ ОКРЕСТНОСТНЫХ МНОЖЕСТВ В ГРАФАХ
Аннотация
В работе вводится и характеризуется класс графов, в которых каждое связное доминирующее множество является (связным) окрестностным, а также класс графов, для каждого связного порожденного подграфа которых мощности наименьшего окрестностного множества и наименьшего связного окрестностного множества совпадают. В предположении P ≠ NP доказана неаппроксимируемость за полиномиальное время с логарифмической гарантированной оценкой точности задачи о наименьшем связном окрестностном множестве в их общем подклассе – классе симплициально-расщепляемых графов.
Список литературы
1. Sampathkumar, E. The neighbourhood number of a graph / E. Sampathkumar, P. S. Neeralagi // Indian J. Pure Appl. Math. – 1985. – Vol. 16. – P. 126–132.
2. Sampathkumar, E. The connected domination number of a graph / E. Sampathkumar, H. B. Walikar // J. Math. Phys. Sci. – 1979. – Vol. 13. – P. 607–613.
3. Sampathkumar, E. Independent, perfect and connected neighbourhood numbers of a graph / E. Sampathkumar, P. S. Neeralagi // J. Comb. Inf. Syst. Sci. – 1994. – Vol. 19. – P. 139–145.
4. Картынник, Ю. А. Доминантно-треугольные графы и графы верхних границ / Ю. А. Картынник, Ю. Л. Орлович // Докл. Нац. акад. наук Беларуси. – 2014. – Т. 58, № 1. – С. 16– 25.
5. Földes, S. Split graphs / S. Földes, P. L. Hammer // Congress. Numer. – 1978. – No. 19. – P. 311–315.
6. Тышкевич, Р. И. Каноническое разложение графа, определяемого степенями его вершин / Р. И. Тышкевич, А. А. Черняк // Изв. АН БССР. Сер. физ.-мат. наук. – 1979. – Т. 5. – С. 14–26.
7. Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990.
8. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982.
9. Zverovich, I. E. Perfect connected-dominant graphs / I. E. Zverovich // Discuss. Math. Graph Theory. – 2003. – Vol. 23. – P. 159–162.