|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Суммарная величина вершинного разделения графа
П. А. Головач
Аннотация:
Вводится новый инвариант графов, названный нами суммарной величиной вершинного разделения. Показано, что задача распознавания, состоящая в том, чтобы по графу $G$ и неотрицательному целому числу $k$ проверить, верно ли, что $\operatorname{sv}(G)\le k$, где $\operatorname{sv}(G)$ — суммарная величина вершинного разделения графа $G$, является NP-полной даже для реберных графов. Решается задача вычисления данного инварианта для графов интервалов. Рассмотрен также вопрос о суммарной величине вершинного разделения деревьев.
Работа выполнена при поддержке программой Университеты России.
Статья поступила: 25.05.1994
Образец цитирования:
П. А. Головач, “Суммарная величина вершинного разделения графа”, Дискрет. матем., 9:4 (1997), 86–91; Discrete Math. Appl., 7:6 (1997), 631–636
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm506https://doi.org/10.4213/dm506 https://www.mathnet.ru/rus/dm/v9/i4/p86
|
Статистика просмотров: |
Страница аннотации: | 425 | PDF полного текста: | 210 | Первая страница: | 1 |
|