4551
правка
Редукция данных для доминирования в графах: различия между версиями
Перейти к навигации
Перейти к поиску
Редукция данных для доминирования в графах (посмотреть исходный код)
Версия от 01:07, 25 марта 2013
, 25 марта 2013→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «Ключевые слова и синонимы: доминирующее множество; редукция до ядра задачи; [[кернелиз…») |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Задача 1 (доминирующее множество) | Задача 1 (доминирующее множество) | ||
Дано: неориентированный граф G = (V, E) и целое число k > 0. | Дано: неориентированный граф G = (V, E) и целое число k > 0. | ||
Вопрос: существует ли подграф S С V с jSj < k, такой, что каждая вершина v 2 V входит в S, либо по крайней мере один из ее соседей входит в S? | Вопрос: существует ли подграф S С V с jSj < k, такой, что каждая вершина v 2 V входит в S, либо по крайней мере один из ее соседей входит в S? | ||