|
Дискретная математика, 1990, том 2, выпуск 3, страницы 90–96
(Mi dm871)
|
|
|
|
Эта публикация цитируется в 15 научных статьях (всего в 15 статьях)
О сложности определения числа доминированля в моногенных классах графов
Д. В. Коробицын
Аннотация:
Задача “доминирующее множество” (ДМ) состоит в том, чтобы для произвольного графа из заданного класса указать мощность минимального доминирующего множества. В статье исследуется задача ДМ на различных классах графов. Классы описываются при помощи конечного множества запрещенных порожденных подграфов. Выводятся достаточные
условия, при помощи которых по виду запрещающего множества можно определить полиномиальную полноту задачи ДМ на соответствующем классе графов. Дается критерий, который позволяет однозначно определять, является задача ДМ полиномиально полной или полиномиально простой на классах графов, которые описываются только одним запрещенным порожденным подграфом.
Статья поступила: 05.09.1989
Образец цитирования:
Д. В. Коробицын, “О сложности определения числа доминированля в моногенных классах графов”, Дискрет. матем., 2:3 (1990), 90–96; Discrete Math. Appl., 2:2 (1992), 191–199
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm871 https://www.mathnet.ru/rus/dm/v2/i3/p90
|
Статистика просмотров: |
Страница аннотации: | 453 | PDF полного текста: | 199 | Первая страница: | 1 |
|