Доминирующий набор

Подмножество узлов графа, такое, что все остальные узлы связаны по крайней мере с одним

Три доминирующих множества одного и того же графа (красного цвета). Число доминирования этого графа равно 2: (b) и (c) показывают, что существует доминирующее множество с 2 вершинами, и не существует доминирующего множества с только 1 вершиной.

В теории графов доминирующее множество для графа G — это подмножество D его вершин, такое, что любая вершина G принадлежит D или имеет соседа в D. Число доминирования γ ( G ) — это число вершин в наименьшем доминирующем множестве для G .

Задача доминирующего множества касается проверки того, что γ( G ) ≤ K для заданного графа G и входного K ; это классическая NP-полная задача принятия решений в теории сложности вычислений . ^[1] Поэтому считается, что не может быть эффективного алгоритма , который может вычислить γ( G ) для всех графов G . Однако существуют эффективные алгоритмы приближения , а также эффективные точные алгоритмы для определенных классов графов.

Доминирующие наборы представляют практический интерес в нескольких областях. В беспроводных сетях доминирующие наборы используются для поиска эффективных маршрутов в мобильных сетях ad-hoc. Они также использовались в реферировании документов и в проектировании защищенных систем для электрических сетей .

Формальное определение

Для неориентированного графа G = ( V , E ) подмножество вершин называется доминирующим множеством , если для каждой вершины существует вершина такая, что . ${\displaystyle D\subseteq V}$ ${\displaystyle u\in V\setminus D}$ ${\displaystyle v\in D}$ ${\displaystyle (u,v)\in E}$

Каждый граф имеет по крайней мере одно доминирующее множество: если множество всех вершин, то по определению D является доминирующим множеством, поскольку вершины нет . Более интересная задача — найти небольшие доминирующие множества. Число доминирования графа G определяется как: . ${\displaystyle D=V=}$ ${\displaystyle u\in V\setminus D}$ ${\displaystyle \gamma (G):=\min\{|D|:D{\text{ is a dominating set of }}G\}}$

Варианты

Связный доминирующий набор — это доминирующий набор, который также является связным . Если S — связный доминирующий набор, можно сформировать остовное дерево G , в котором S образует множество нелистовых вершин дерева; наоборот, если T — любое остовное дерево в графе с более чем двумя вершинами, нелистовые вершины T образуют связный доминирующий набор. Поэтому нахождение минимальных связных доминирующих наборов эквивалентно нахождению остовных деревьев с максимально возможным числом листьев.

Полный доминирующий набор (или сильно доминирующий набор ) — это набор вершин, такой что все вершины в графе, включая вершины в самом доминирующем наборе, имеют соседа в доминирующем наборе. ^[2] То есть: для каждой вершины , существует вершина такая, что . На рисунке (c) выше показано доминирующее множество, которое является связанным доминирующим набором и полным доминирующим набором; примеры на рисунках (a) и (b) не являются ни тем, ни другим. В отличие от простого доминирующего набора, полный доминирующий набор может не существовать. Например, граф с одной или несколькими вершинами и без ребер не имеет полного доминирующего набора. Число сильного доминирования G определяется как: ; очевидно, . ${\displaystyle u\in V}$ ${\displaystyle v\in D}$ ${\displaystyle (u,v)\in E}$ ${\displaystyle \gamma ^{strong}(G):=\min\{|D|:D{\text{ is a strongly-dominating set of }}G\}}$ ${\displaystyle \gamma ^{strong}(G)\geq \gamma (G)}$

Доминирующий набор рёбер — это набор рёбер (пар вершин), объединение которых является доминирующим набором; такой набор может не существовать (например, граф с одной или несколькими вершинами и без рёбер не имеет его). Если он существует, то объединение всех его рёбер является сильно доминирующим набором. Поэтому наименьший размер набора с доминирующим рёбрами составляет не менее . ${\displaystyle \gamma ^{strong}(G)/2}$

Напротив, множество с доминирующими ребрами — это множество D ребер, такое, что каждое ребро, не входящее в D , смежно по крайней мере с одним ребром в D ; такое множество всегда существует (например, множество всех ребер является множеством с доминирующими ребрами).

k -доминирующий набор — это набор вершин, такой, что каждая вершина, не входящая в набор, имеет по крайней мере k соседей в наборе (стандартный доминирующий набор — это 1-доминирующий набор). Аналогично, k -кортежный доминирующий набор — это набор вершин, такой, что каждая вершина в графе имеет по крайней мере k соседей в наборе (полный доминирующий набор — это 1-кортежный доминирующий набор). (1 + log n ) -аппроксимация минимального k -кортежного доминирующего набора может быть найдена за полиномиальное время. ^[3] Каждый граф допускает k -доминирующий набор (например, набор всех вершин); но только графы с минимальной степенью k − 1 допускают k -кортежный доминирующий набор. Однако, даже если граф допускает k -кортежный доминирующий набор, минимальный k -кортежный доминирующий набор может быть почти в k раз больше минимального k -доминирующего набора для того же графа; ^[4] (1,7 + log Δ) -аппроксимацию минимального k -доминирующего множества можно также найти за полиномиальное время.

Звездно -доминирующее множество — это подмножество D множества V , такое, что для каждой вершины v в V звезда v (множество ребер, смежных с v ) пересекает звезду некоторой вершины в D . Очевидно, что если G имеет изолированные вершины , то у него нет звездно-доминирующих множеств (поскольку звезда изолированных вершин пуста). Если G не имеет изолированных вершин, то каждое доминирующее множество является звездно-доминирующим множеством и наоборот. Различие между звездно-доминированием и обычным доминированием становится более существенным, когда рассматриваются их дробные варианты. ^[5]

Доматическое разбиение — это разбиение вершин на непересекающиеся доминирующие множества. Доматическое число — это максимальный размер доматического разбиения.

Вечное доминирующее множество — это динамическая версия доминирования, в которой вершина v в доминирующем множестве D выбирается и заменяется соседом u ( u не входит в D ) таким образом, что измененное D также является доминирующим множеством, и этот процесс может быть повторен для любой бесконечной последовательности выборов вершин  v .

Доминирующие и независимые множества

Доминирующие множества тесно связаны с независимыми множествами : независимое множество также является доминирующим множеством тогда и только тогда, когда оно является максимальным независимым множеством , поэтому любое максимальное независимое множество в графе обязательно является также минимальным доминирующим множеством.

Доминированиекнезависимые наборы

Доминирующий набор может быть или не быть независимым набором. Например, рисунки (a) и (b) выше показывают независимые доминирующие наборы, в то время как рисунок (c) иллюстрирует доминирующий набор, который не является независимым набором.

Независимое доминирующее число i ( G ) графа G — это размер наименьшего доминирующего множества, которое является независимым множеством. Эквивалентно, это размер наименьшего максимального независимого множества. Минимум в i ( G ) берется по меньшему числу элементов (рассматриваются только независимые множества), поэтому γ ( G ) ≤ i ( G ) для всех графов G .

Неравенство может быть строгим — существуют графы G, для которых γ ( G ) < i ( G ) . Например, пусть G — граф двойной звезды , состоящий из вершин ⁠ ⁠ ${\displaystyle x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}}$ , где p , q > 1 . Ребра графа G определяются следующим образом: каждый x _i смежно с a , a смежно с b , а b смежно с каждым y _j . Тогда γ( G ) = 2 , поскольку { a , b } — наименьшее доминирующее множество. Если p ≤ q , то i ( G ) = p + 1 , поскольку ⁠ ⁠ ${\displaystyle \{x_{1},\ldots ,x_{p},b\}}$ — наименьшее доминирующее множество, которое также независимо (это наименьшее максимальное независимое множество).

Существуют семейства графов, в которых γ( G ) = i ( G ) , то есть каждое минимальное максимальное независимое множество является минимальным доминирующим множеством. Например, γ( G ) = i ( G ) , если G является графом без клешней . ^[6]

Граф G называется графом с совершенным доминированием, если γ ( H ) = i ( H ) в каждом индуцированном подграфе H графа G. Поскольку индуцированный подграф графа без клешней является графом без клешней, то каждый граф без клешней также является графом с совершенным доминированием. ^[7]

Для любого графа G его линейный граф L ( G ) не имеет клешней, и, следовательно, минимальное максимальное независимое множество в L ( G ) также является минимальным доминирующим множеством в L ( G ) . Независимое множество в L ( G ) соответствует паросочетанию в G , а доминирующее множество в L ( G ) соответствует множеству, доминирующему по ребру, в G . Поэтому минимальное максимальное паросочетание имеет тот же размер, что и минимальное доминирующее по ребру множество.

Доминированиеизнезависимые наборы

Число доминирования независимости iγ ( G ) графа G — это максимум среди всех независимых множеств A графа G наименьшего множества, доминирующего над A . ^[8] Доминирование подмножеств вершин требует потенциально меньше вершин, чем доминирование над всеми вершинами, поэтому iγ ( G ) ≤ γ ( G ) для всех графов G .

Неравенство может быть строгим — существуют графы G, для которых iγ ( G ) < γ ( G ) . Например, для некоторого целого числа n пусть G будет графом, в котором вершинами являются строки и столбцы доски n -на- n , и две такие вершины связаны тогда и только тогда, когда они пересекаются. Единственными независимыми множествами являются множества, состоящие только из строк или множества, состоящие только из столбцов, и каждое из них может доминироваться одной вершиной (столбцом или строкой), поэтому iγ ( G ) = 1 . Однако, чтобы доминировать над всеми вершинами, нам нужны по крайней мере одна строка и один столбец, поэтому γ ( G ) = 2 . Более того, отношение между γ ( G ) / iγ ( G ) может быть сколь угодно большим. Например, если вершины G являются всеми подмножествами квадратов доски n на n , то все равно iγ ( G ) = 1 , но γ ( G ) = n . ^[8]

Число двунезависимого доминирования iγi ( G ) графа G — это максимум среди всех независимых множеств A графа G наименьшего независимого множества, доминирующего над A . Для любого графа G справедливы следующие соотношения : $${\displaystyle {\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{aligned}}}$$

История

Проблема доминирования изучалась с 1950-х годов, но темпы исследований доминирования значительно возросли в середине 1970-х годов. В 1972 году Ричард Карп доказал, что задача покрытия множеств является NP-полной . Это имело непосредственные последствия для задачи доминирующего множества, поскольку между этими двумя задачами существуют прямые биекции вершина-множество и ребро-неразъединяющееся-пересечение. Это доказало, что задача доминирующего множества также является NP-полной . ^[9]

Алгоритмы и вычислительная сложность

Задача покрытия множеств является хорошо известной NP-трудной задачей — версия решения покрытия множеств была одной из 21 NP-полных задач Карпа . Существует пара полиномиальных по времени L-редукций между задачей минимального доминирующего множества и задачей покрытия множеств . ^[10] Эти редукции (см. ниже) показывают, что эффективный алгоритм для задачи минимального доминирующего множества обеспечит эффективный алгоритм для задачи покрытия множеств, и наоборот. Более того, редукции сохраняют отношение аппроксимации : для любого α, полиномиальный по времени алгоритм α-аппроксимации для минимальных доминирующих множеств обеспечит полиномиальный по времени алгоритм α-аппроксимации для задачи покрытия множеств, и наоборот. Обе задачи фактически являются Log-APX-полными . ^[11]

Аппроксимируемость покрытия множеств также хорошо понятна: логарифмический фактор аппроксимации может быть найден с помощью простого жадного алгоритма , а нахождение сублогарифмического фактора аппроксимации является NP-трудной задачей. Более конкретно, жадный алгоритм обеспечивает фактор 1 + log| V | аппроксимации минимального доминирующего множества, и никакой алгоритм с полиномиальным временем не может достичь фактора аппроксимации лучше, чем c log| V | для некоторого c > 0 , если только P = NP . ^[12]

L-редукции

Следующие два сведения показывают, что задача минимального доминирующего множества и задача покрытия множества эквивалентны относительно L-редукций : имея экземпляр одной задачи, мы можем построить эквивалентный экземпляр другой задачи. ^[10]

От доминирующего сета до покрытия сета

Для данного графа G = ( V , E ) с V = {1, 2, ..., n } построим экземпляр покрытия множеств ( U , S ) следующим образом: вселенная U — это V , а семейство подмножеств — это S = { S1 , S2 _, ..., Sn _} , такое, что _Sv состоит из вершины v и _всех вершин , смежных с v в G.

Теперь, если D является доминирующим множеством для G , то C = { S _v  : v ∈ D } является допустимым решением задачи покрытия множеств, при этом | C | = | D | . Обратно, если C = { S _v  : v ∈ D } является допустимым решением задачи покрытия множеств, то D является доминирующим множеством для G , при этом | D | = | C | .

Следовательно, размер минимального доминирующего множества для G равен размеру минимального покрытия множества для ( U , S ) . Более того, существует простой алгоритм, который отображает доминирующее множество в покрытие множества того же размера и наоборот. В частности, эффективный алгоритм α-аппроксимации для покрытия множества обеспечивает эффективный алгоритм α-аппроксимации для минимальных доминирующих множеств.

Например, учитывая граф G, показанный справа, мы строим экземпляр покрытия множеств с вселенной U = {1, 2, ..., 6} и подмножествами S ₁ = {1, 2, 5}, S ₂ = {1, 2, 3, 5}, S ₃ = {2, 3, 4, 6}, S ₄ = {3, 4}, S ₅ = {1, 2, 5, 6} и S ₆ = {3, 5, 6}. В этом примере D = {3, 5} является доминирующим множеством для G – это соответствует покрытию множеств C = { S ₃ , S ₅ }. Например, вершина 4 ∈ V доминируется вершиной 3 ∈ D , а элемент 4 ∈ U содержится в множестве S ₃ ∈ C .

От покрытия сета до доминирования сета

Пусть ( S , U ) — пример задачи покрытия множеств с универсумом U и семейством подмножеств S = { S _i  : i ∈ I }; мы предполагаем, что U и множество индексов I не пересекаются. Построим граф G = ( V , E ) следующим образом: множество вершин равно V = I ∪ U , между каждой парой i , j ∈ I есть ребро { i , j } ∈ E , а также есть ребро { i , u } для каждого i ∈ I и u ∈ S _i . То есть G — это разделенный граф : I — клика , а U — независимое множество .

Теперь, если C = { S _i  : i ∈ D } является допустимым решением задачи покрытия множеств для некоторого подмножества D ⊆ I , то D является доминирующим множеством для G , причем | D | = | C | : Во-первых, для каждого u ∈ U существует i ∈ D такой, что u ∈ S _i , и по построению u и i смежны в G ; следовательно, u доминируется i . Во-вторых, поскольку D должно быть непустым, каждое i ∈ I смежно с вершиной в D .

Обратно, пусть D — доминирующее множество для G. Тогда можно построить другое доминирующее множество X , такое что | X | ≤ | D | и X ⊆ I : просто замените каждый u ∈ D ∩ U соседним i ∈ I элемента u . Тогда C = { S _i  : i ∈ X } — допустимое решение задачи покрытия множеств, при этом | C | = | X | ≤ | D | .

На рисунке справа показана конструкция для U = { a , b , c , d , e }, I = {1, 2, 3, 4}, _S1 = { a , b , c }, _S2 = { a , b } , S3 = { b , c , d } и S4 = { c _, d _, e } .

В этом примере C = { S ₁ , S ₄ } — это покрытие множеств; это соответствует доминирующему множеству D = {1, 4}.

D = { a , 3, 4} — еще одно доминирующее множество для графа G. При наличии D можно построить доминирующее множество _X = { ₁ , 3, 4}, которое не больше D _и является подмножеством I. Доминирующее множество X соответствует покрытию множеств C = { S1 , S3 , S4 }.

Особые случаи

Если граф имеет максимальную степень Δ, то алгоритм жадной аппроксимации находит O (log Δ) -аппроксимацию минимального доминирующего множества. Также, пусть d _g будет мощностью доминирующего множества, полученного с помощью жадной аппроксимации, тогда выполняется следующее соотношение, , где N — число узлов, а M — число ребер в данном неориентированном графе. ^[13] Для фиксированного Δ это квалифицируется как доминирующее множество для членства в APX ; на самом деле, оно является APX-полным. ^[14] ${\displaystyle d_{g}\leq N+1-{\sqrt {2M+1}}}$

Задача допускает схему аппроксимации за полиномиальное время (PTAS) для особых случаев, таких как графы единичных дисков и планарные графы . ^[15] Минимальное доминирующее множество может быть найдено за линейное время в последовательно-параллельных графах . ^[16]

Точные алгоритмы

Минимальное доминирующее множество n -вершинного графа может быть найдено за время O (2 ⁿ n ) путем проверки всех подмножеств вершин. Фомин, Грандони и Кратч (2009) показывают, как найти минимальное доминирующее множество за время O (1,5137 ⁿ ) и экспоненциальное пространство, а также за время O (1,5264 ⁿ ) и полиномиальное пространство. Более быстрый алгоритм, использующий время O (1,5048 ⁿ ) был найден ван Ройем, Недерлофом и ван Дейком (2009), которые также показывают, что количество минимальных доминирующих множеств может быть вычислено за это время. Количество минимальных доминирующих множеств не превышает 1,7159 ⁿ , и все такие множества могут быть перечислены за время O (1,7159 ⁿ ) . ^[17]

Параметризованная сложность

Нахождение доминирующего множества размера k играет центральную роль в теории параметризованной сложности. Это наиболее известная задача, полная для класса W[2], и она используется во многих редукциях для демонстрации неразрешимости других задач. В частности, задача не является разрешимой с фиксированными параметрами в том смысле, что не существует алгоритма со временем выполнения f ( k ) n ^O(1) для любой функции f , если только W-иерархия не схлопнется до FPT=W[2].

С другой стороны, если входной граф плоский , задача остается NP-трудной, но известен алгоритм с фиксированными параметрами. Фактически, задача имеет ядро ​​линейного размера по k ^[18] , а время выполнения, экспоненциальное по √ k и кубическое по n, может быть получено путем применения динамического программирования к разложению ветвей ядра. ^[19] В более общем смысле, задача доминирующего множества и многие варианты задачи являются разрешимыми с фиксированными параметрами, если параметризованы как размером доминирующего множества, так и размером наименьшего запрещенного полного двудольного подграфа ; то есть задача является FPT на графах без бикли , очень общем классе разреженных графов, который включает планарные графы. ^[20]

Дополнительный набор к доминирующему набору, неблокирующий , может быть найден с помощью алгоритма с фиксированными параметрами на любом графе. ^[21]

Смотрите также

• Гипотеза Визинга связывает число доминирования декартова произведения графов с числом доминирования его сомножителей.
• Установить проблему покрытия
• Число рабства
• Неблокирующий — дополнение доминирующего набора.

Примечания

1. Гэри и Джонсон (1979).
2. Уэст (2001), Раздел 3.1.
3. Класинг и Лафорест (2004).
4. Фёрстер (2013).
5. Мешулам, Рой (2003-05-01). «Числа доминирования и гомология». Журнал комбинаторной теории, серия A. 102 ( 2): 321–330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN  0097-3165.
6. Аллан и Ласкар (1978).
7. Фодри, Фландрен и Рыячек (1997).
8. Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах». Комбинаторика . 27 (3): 253–267. doi : 10.1007/s00493-007-2086-y. ISSN  1439-6912. S2CID  43510417.
9. Хедетниеми и Ласкар (1990).
10. Канн (1992), стр. 108–109.
11. Эскофье и Пашос (2006).
12. Раз и Сафра (1997).
13. Парех (1991).
14. Пападимитриу и Яннакакис (1991).
15. Крещенци и др. (2000).
16. Такамизава, Нисидзеки и Сайто (1982).
17. Фомин и др. (2008).
18. Альбер, Fellows & Niedermeier (2004).
19. Фомин и Тиликос (2006).
20. Телле и Вилланджер (2012).
21. Дене и др. (2006).

Ссылки

• Альбер, Йохен; Феллоуз, Майкл Р .; Нидермейер, Рольф (2004), «Сокращение данных за полиномиальное время для доминирующего набора», Журнал ACM , 51 (3): 363–384, arXiv : cs/0207066 , doi :10.1145/990308.990309, S2CID  488501.
• Аллан, Роберт Б.; Ласкар, Рену (1978), «О доминировании и независимых числах доминирования графа», Дискретная математика , 23 (2): 73–76, doi : 10.1016/0012-365X(78)90105-X.
• Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Вегингер, Герхард (2000), «Минимальный доминирующий набор», Сборник задач оптимизации NP.
• Dehne, Frank; Fellows, Michael; Fernau, Henning; Prieto, Elena ; Rosamond, Frances (2006), "Nonblocker: Parameterized algorithmics for minimum dominating set" (PDF) , SOFSEM 2006: 32-я конференция по текущим тенденциям в теории и практике компьютерных наук, Мерин, Чешская Республика, 21-27 января 2006 г., Труды , Lecture Notes in Computer Science, т. 3831, Springer, стр. 237–245, doi :10.1007/11611257_21, ISBN 978-3-540-31198-0.
• Эскофье, Бруно; Пашос, Вангелис Т. (2006), «Полнота в классах аппроксимации за пределами APX» (PDF) , Теоретическая информатика , 359 (1–3): 369–377, doi : 10.1016/j.tcs.2006.05.023
• Faudree, Ralph ; Flandrin, Evelyne ; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , MR  1432221.
• Фомин, Федор В.; Грандони, Фабрицио; Кратч, Дитер (2009), «Метод измерения и завоевания для анализа точных алгоритмов», Журнал ACM , 56 (5): 25:1–32, doi :10.1145/1552285.1552286, S2CID  1186651.
• Фомин, Федор В.; Грандони, Фабрицио; Пяткин, Артем; Степанов, Алексей (2008), «Комбинаторные границы с помощью измерения и завоевания: ограничение минимальных доминирующих множеств и их применение», ACM Transactions on Algorithms , 5 (1): 9:1–17, doi :10.1145/1435375.1435384, S2CID  2489447.
• Фомин, Федор В.; Тиликос, Димитриос М. (2006), «Доминирующие множества в планарных графах: ширина ветвей и экспоненциальное ускорение», SIAM Journal on Computing , 36 (2): 281, doi :10.1137/S0097539702419649, S2CID  5232238.
• Фёрстер, Клаус-Тихо. (2013), «Аппроксимация отказоустойчивого доминирования в общих графах», Труды Десятого семинара по аналитической алгоритмике и комбинаторике ANALCO , SIAM, стр. 25–32, doi : 10.1137/1.9781611973037.4, ISBN 978-1-61197-254-2.
• Garey, Michael R .; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. MR  0519066. OCLC  247570676., стр. 190, задача GT2.
• Хедетниеми, СТ; Ласкар, Р.К. (1990), «Библиография по доминированию в графах и некоторые основные определения параметров доминирования», Дискретная математика , 86 (1–3): 257–277, doi : 10.1016/0012-365X(90)90365-O.
• Канн, Вигго (1992), Об аппроксимируемости NP-полных задач оптимизации (PDF) . Кандидатская диссертация, кафедра численного анализа и вычислительной науки, Королевский технологический институт , Стокгольм{{citation}}: CS1 maint: постскриптум ( ссылка ).
• Класинг, Ральф; Лафорест, Кристиан (2004), «Результаты испытаний на прочность и алгоритмы аппроксимации доминирования k-кортежей в графах», Information Processing Letters , 89 (2): 75–83, doi :10.1016/j.ipl.2003.10.004.
• Пападимитриу, Христос Х.; Яннакакис, Михайлис (1991), «Оптимизация, аппроксимация и классы сложности», Журнал компьютерных и системных наук , 43 (3): 425–440, doi :10.1016/0022-0000(91)90023-X
• Парех, Абхай К. (1991), «Анализ жадной эвристики для поиска небольших доминирующих множеств в графах», Information Processing Letters , 39 (5): 237–240, doi : 10.1016/0020-0190(91)90021-9, hdl : 1721.1/1201
• Раз, Р.; Сафра, С. (1997), «Тест низкой степени с субконстантной вероятностью ошибки и характеристика PCP с субконстантной вероятностью ошибки для NP», Труды 29-го ежегодного симпозиума ACM по теории вычислений , ACM, стр. 475–484, doi :10.1145/258533.258641, ISBN 0-89791-888-6, S2CID  15457604.
• Такамидзава, К.; Нисидзеки, Т .; Сайто, Н. (1982), «Вычислимость комбинаторных задач на последовательно-параллельных графах за линейное время», Журнал ACM , 29 (3): 623–641, doi : 10.1145/322326.322328 , S2CID  16082154.
• Telle, Jan Arne; Villanger, Yngve (2012), "FPT-алгоритмы для доминирования в графах без бикликов", в Epstein, Leah; Ferragina, Paolo (ред.), Algorithms – ESA 2012: 20th Annual European Symposium, Любляна, Словения, 10–12 сентября 2012 г., Труды , Lecture Notes in Computer Science , т. 7501, Springer, стр. 802–812, doi :10.1007/978-3-642-33090-2_69, ISBN 978-3-642-33089-6.
• ван Рой, JMM; Недерлоф, Дж.; ван Дейк, Т.К. (2009), «Включение/исключение соответствует измерению и победе: точные алгоритмы подсчета доминирующих наборов», Proc. 17-й ежегодный европейский симпозиум по алгоритмам, ESA 2009 , Конспекты лекций по информатике, том. 5757, Springer, стр. 554–565, номер документа : 10.1007/978-3-642-04128-0_50, ISBN. 978-3-642-04127-3.

Дальнейшее чтение

• Грандони, Ф. (2006), «Заметка о сложности минимального доминирующего множества», Журнал дискретных алгоритмов , 4 (2): 209–214, CiteSeerX  10.1.1.108.3223 , doi :10.1016/j.jda.2005.03.002.
• Гуха, С.; Хуллер, С. (1998), «Аппроксимационные алгоритмы для связанных доминирующих множеств» (PDF) , Algorithmica , 20 (4): 374–387, doi :10.1007/PL00009201, hdl : 1903/830 , S2CID  1249122.
• Хейнс, Тереза ​​В .; Хедетниеми, Стивен; Слейтер, Питер (1998a), Основы доминирования в графах , Марсель Деккер, ISBN 0-8247-0033-3, OCLC  37903553.
• Хейнс, Тереза ​​В.; Хедетниеми, Стивен; Слейтер, Питер (1998b), Доминирование в графах: продвинутые темы , Марсель Деккер, ISBN 0-8247-0034-1, OCLC  38201061.
• Уэст, Дуглас Б. (2001), Введение в теорию графов (2-е изд.), Pearson Education.