4551
правка
Редукция данных для доминирования в графах: различия между версиями
Перейти к навигации
Перейти к поиску
Редукция данных для доминирования в графах (посмотреть исходный код)
Версия от 01:36, 25 марта 2013
, 25 марта 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
'''Теорема 1. Планарный граф G = (V, E) может быть за полиномиальное время приведен при помощи редукции к планарному графу G' = (V', E'), такому, что G имеет доминирующее множество размера k в том и только том случае, если G0 имеет доминирующее множество размера k и |V'| = O(k).''' | '''Теорема 1. Планарный граф G = (V, E) может быть за полиномиальное время приведен при помощи редукции к планарному графу G' = (V', E'), такому, что G имеет доминирующее множество размера k в том и только том случае, если G0 имеет доминирующее множество размера k и |V'| = O(k).''' | ||
Иными словами, теорема утверждает, что задача нахождения доминирующего множества в планарных графах (DOMINATING SET) имеет ядро линейного размера. Значение верхней границы | | Иными словами, теорема утверждает, что задача нахождения доминирующего множества в планарных графах (DOMINATING SET) имеет ядро линейного размера. Значение верхней границы |V'| вначале было установлено равным 335k [5], затем снижено до 67k [7]. Эти результаты могут быть расширены на графы ограниченного рода [10]. Кроме того, подобные же результаты (линейная кернелизация) были недавно получены для задачи нахождения полноразмерного остовного дерева в планарном графе (FULL-DEGREE SPANNING TREE) [13]. Впоследствии эти результаты были обобщены в виде методологической схемы [12]. | ||
== Применение == | == Применение == | ||