Preview

Известия Национальной академии наук Беларуси. Серия физико-математических наук

Расширенный поиск

АЛГОРИТМИЧЕСКИЕ СВОЙСТВА СВЯЗНЫХ ОКРЕСТНОСТНЫХ МНОЖЕСТВ В ГРАФАХ

Аннотация

В работе вводится и характеризуется класс графов, в которых каждое связное доминирующее множество является (связным) окрестностным, а также класс графов, для каждого связного порожденного подграфа которых мощности наименьшего окрестностного множества и наименьшего связного окрестностного множества совпадают. В предположении 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.


Рецензия

Просмотров: 667


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-2430 (Print)
ISSN 2524-2415 (Online)