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

О Доминаторе в графах потока управления см. Доминатор (теория графов) .

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

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

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

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

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

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

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

Варианты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Число доминирования независимости iγ ( G ) графа G является максимальным среди всех независимых множеств из G наименьшего множества, доминирующего над A. A Для доминирования подмножеств вершин требуется потенциально меньше вершин, чем для доминирования всех вершин, поэтому 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 .

Двунезависимое число доминирования iγi ( G ) графа G является максимальным среди всех независимых множеств A из G наименьшего независимого множества, доминирующего A. над выполняются следующие соотношения Для любого графа G : $${\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-полной . Это доказало, что задача о доминирующем множестве также

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

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

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

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

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

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

Учитывая граф 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 } ∈ E , между каждой парой i , j ∈ I , а также существует ребро { я , ты } для каждого я € I и ты € S _я . То есть G — расщепленный граф : I — клика , а U — независимое множество .

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

В этом примере 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 — мощность доминирующего множества, полученная с использованием жадной аппроксимации, тогда справедливо следующее соотношение: $d_{g}\leq N+1-{\sqrt {2M+1}}$, где N — количество узлов, а M — количество ребер в данном неориентированном графе. Для фиксированного Δ это квалифицируется как доминирующий набор для в APX членства ; фактически, он APX-полный.

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

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

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

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

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

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

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

См. также

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

Ссылки

• Альбер, Йохен; Товарищи, Майкл Р .; Нидермейер, Рольф (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 , ISBN.  978-3-540-31198-0 .
• Эскофье, Бруно; Пашос, Вангелис Т. (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:postscript ( ссылка ) .
• Класинг, Ральф; Лафорест, Кристиан (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 с субконстантной вероятностью ошибки", 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, doi : 10.1007/978-3-642-33090-2_69 , ISBN.  978-3-642-33089-6 .
• ван Рой, JMM; Недерлоф, Дж.; ван Дейк, TC (2009), «Включение/исключение соответствует измерению и победе: точные алгоритмы подсчета доминирующих множеств», Proc. 17-й ежегодный европейский симпозиум по алгоритмам, ESA 2009 , Конспекты лекций по информатике, том. 5757, Спрингер, стр. 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 .