4551
правка
Редукция данных для доминирования в графах: различия между версиями
Перейти к навигации
Перейти к поиску
Редукция данных для доминирования в графах (посмотреть исходный код)
Версия от 01:35, 25 марта 2013
, 25 марта 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
Рассмотрим вершину <math>w \in N_3(v) \; </math>. Такая вершина имеет соседей только из <math> \{ v \} \cup N_1(v) \cup N_3(v) \; </math>. Следовательно, для того, чтобы доминировать вершину w, по меньшей мере одна вершина из <math> \{ v \} \cup N_1(v) \cup N_3(v) \; </math> должна входить в доминирующее множество входного графа. Поскольку v может доминировать все вершины, которые были бы доминированы в результате выбора из <math>N_1(v) \cup N_3(v) \; </math> в доминирующее множество, это дает следующее правило редукции данных: | Рассмотрим вершину <math>w \in N_3(v) \; </math>. Такая вершина имеет соседей только из <math> \{ v \} \cup N_1(v) \cup N_3(v) \; </math>. Следовательно, для того, чтобы доминировать вершину w, по меньшей мере одна вершина из <math> \{ v \} \cup N_1(v) \cup N_3(v) \; </math> должна входить в доминирующее множество входного графа. Поскольку v может доминировать все вершины, которые были бы доминированы в результате выбора из <math>N_1(v) \cup N_3(v) \; </math> в доминирующее множество, это дает следующее правило редукции данных: | ||
Новая вершина | Если <math>N_3(v) \ne \emptyset \; </math> для некоторой вершины v, удалить <math>N_2(v) \; </math> и <math>N_3(v) \; </math> из G и добавить в G новую вершину v' с дугой {v, v'}. | ||
Новая вершина v' может рассматриваться как «вершина-гаджет», которая «заставляет» выбрать v в доминирующее множество. Корректность этого правила нетрудно проверить, поскольку она сводится к тому, что исходный граф имеет доминирующее множество размера k в том и только том случае, если приведенный в результате редукции граф имеет доминирующее множество размера k. Очевидно, что редукция данных может быть проведена за полиномиальное время [5]. Однако существуют «ромбовидные» структуры, к которым данное правило редукции неприменимо. Для них было предложено несколько более сложное правило, основанное на рассмотрении объединенной окрестности двух вершин [5]. | |||
В [5] была доказана справедливость следующей теоремы. | В [5] была доказана справедливость следующей теоремы. | ||
Теорема 1. Планарный граф G = (V, E) может быть за полиномиальное время приведен при помощи редукции к планарному графу | |||
'''Теорема 1. Планарный граф G = (V, E) может быть за полиномиальное время приведен при помощи редукции к планарному графу G' = (V', E'), такому, что G имеет доминирующее множество размера k в том и только том случае, если G0 имеет доминирующее множество размера k и |V'| = O(k).''' | |||
Иными словами, теорема утверждает, что задача нахождения доминирующего множества в планарных графах (DOMINATING SET) имеет ядро линейного размера. Значение верхней границы |V0| вначале было установлено равным 335k [5], затем снижено до 67k [7]. Эти результаты могут быть расширены на графы ограниченного рода [10]. Кроме того, подобные же результаты (линейная кернелизация) были недавно получены для задачи нахождения полноразмерного остовного дерева в планарном графе (FULL-DEGREE SPANNING TREE) [13]. Впоследствии эти результаты были обобщены в виде методологической схемы [12]. | Иными словами, теорема утверждает, что задача нахождения доминирующего множества в планарных графах (DOMINATING SET) имеет ядро линейного размера. Значение верхней границы |V0| вначале было установлено равным 335k [5], затем снижено до 67k [7]. Эти результаты могут быть расширены на графы ограниченного рода [10]. Кроме того, подобные же результаты (линейная кернелизация) были недавно получены для задачи нахождения полноразмерного остовного дерева в планарном графе (FULL-DEGREE SPANNING TREE) [13]. Впоследствии эти результаты были обобщены в виде методологической схемы [12]. | ||