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

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

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

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

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

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

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

Для неориентированного графа 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 — двойной звездчатый граф, состоящий из вершин , где p , q > 1 . Ребра G определяются следующим образом: каждое _xi смежно с a , a смежно с b , а b смежно с _каждым yj . Тогда γ( G ) = 2 , поскольку { a , b } — наименьшее доминирующее множество. Если p ≤ q , то i ( G ) = p + 1, поскольку это наименьшее доминирующее множество, которое также является независимым (это наименьшее максимальное независимое множество). ${\displaystyle x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}}$ ${\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 x n , и две такие вершины соединены тогда и только тогда, когда они пересекаются. Единственными независимыми множествами являются наборы только строк или наборы только столбцов, и в каждом из них может доминировать одна вершина (столбец или строка), поэтому iγ ( G ) = 1 . Однако, чтобы доминировать над всеми вершинами, нам нужна хотя бы одна строка и один столбец, поэтому γ ( G ) = 2 . Более того, отношение между γ ( G )/ iγ ( G ) может быть сколь угодно большим. Например, если все вершины G являются подмножествами квадратов доски размером n x 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| В | аппроксимация минимального доминирующего набора, и ни один алгоритм с полиномиальным временем не может достичь коэффициента аппроксимации лучше, чем c log| В | для некоторого c > 0 , если только P = NP . ^[12]

L-сокращения

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

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

Учитывая граф G = ( V , E ) с V = {1, 2, ..., n }, постройте экземпляр покрытия множества ( U , S ) следующим образом: вселенная U - это V , а семейство подмножеств - это S = { S ₁ , S ₂ , ..., S _n } такой, что S _v состоит из вершины v и всех смежных с v вершин в G .

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

Следовательно, размер минимального доминирующего множества для 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 и ты € S _я . То есть G — расщепленный граф : I — клика , а U — независимое множество .

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

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

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

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

D = { a , 3, 4} — еще одно доминирующее множество графа G. Учитывая D , мы можем построить доминирующее множество X = {1, 3, 4} ,которое не больше D и которое является подмножеством I. Доминирующему множеству X соответствует покрытие множества C = { S ₁ , S ₃ , S ₄ }.

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

Если граф имеет максимальную степень Δ, то жадный алгоритм аппроксимации находит 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. Мешулам, Рой (1 мая 2003 г.). «Числа доминирования и гомологии». Журнал комбинаторной теории, серия А. 102 (2): 321–330. дои : 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), «Сокращение данных за полиномиальное время для доминирующего набора», Journal of the ACM , 51 (3): 363–384, arXiv : cs/0207066 , doi : 10.1145/990308.990309, S2CID  488501.
• Аллан, Роберт Б.; Ласкар, Рену (1978), «О доминировании и независимых числах доминирования графа», Discrete Mathematics , 23 (2): 73–76, doi : 10.1016/0012-365X(78)90105-X.
• Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Вегингер, Герхард (2000), «Минимальный доминирующий набор», Сборник задач оптимизации NP.
• Дене, Франк; Ребята, Майкл; Фернау, Хеннинг; Прието, Елена; Розамонд, Фрэнсис (2006), «Неблокирующий: параметризованная алгоритмика для минимального доминирующего набора» (PDF) , SOFSEM 2006: 32-я конференция по текущим тенденциям в теории и практике информатики, Мерин, Чешская Республика, 21-27 января 2006 г., материалы , Конспекты лекций по информатике, вып. 3831, Springer, стр. 237–245, номер документа : 10.1007/11611257_21..
• Эскофье, Бруно; Пашос, Вангелис Т. (2006), «Полнота в классах аппроксимации за пределами APX» (PDF) , Theoretical Computer Science , 359 (1–3): 369–377, doi : 10.1016/j.tcs.2006.05.023
• Фаудри, Ральф ; Фландрин, Эвелин; Рыячек, Зденек (1997), «Графы без клешней — обзор», 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), «Аппроксимация отказоустойчивого доминирования в общих графах», Proc. Десятого семинара по аналитической алгоритмике и комбинаторике ANALCO , SIAM, стр. 25–32, doi : 10.1137/1.9781611973037.4, ISBN 978-1-61197-254-2.
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. МР  0519066. OCLC  247570676., п. 190, проблема GT2.
• Хедетниеми, СТ; Ласкар, Р.К. (1990), «Библиография по доминированию в графах и некоторые основные определения параметров доминирования», Discrete Mathematics , 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), "Тест низкой степени субпостоянной вероятности ошибки и характеристика NP с субпостоянной вероятностью ошибки PCP", Proc. 29-й ежегодный симпозиум ACM по теории вычислений , ACM, стр. 475–484, doi : 10.1145/258533.258641, ISBN 0-89791-888-6, S2CID  15457604.
• Такамизава, К.; Нишизеки, Т. ; Сайто, Н. (1982), «Вычислимость комбинаторных задач на последовательно-параллельных графах за линейное время», Journal of the ACM , 29 (3): 623–641, doi : 10.1145/322326.322328 , S2CID  16082154.
• Телле, Ян Арне; Вилланджер, Ингве (2012), «Алгоритмы FPT для доминирования в графах без биклик», в Эпштейне, Лия; Феррагина, Паоло (ред.), Алгоритмы - ESA 2012: 20-й ежегодный европейский симпозиум, Любляна, Словения, 10–12 сентября 2012 г., Труды , Конспекты лекций по информатике , том. 7501, Springer, стр. 802–812, номер документа : 10.1007/978-3-642-33090-2_69..
• ван Рой, 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.