Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для Dominator в графах потока управления см. Dominator (теория графов) .
Доминирующие множества (красные вершины).

В теории графов , A доминирующее множество для графа G  = ( V ,  E ) является подмножество D из V таким образом, что каждая вершина не в D примыкает , по меньшей мере , одного члена D . Число доминирование γ ( G ) есть число вершин в наименьшей доминирующий набор для  G .

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

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

История [ править ]

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

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

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

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

Доминирование на независимых множеств [ править ]

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

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

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

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

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

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

Доминирование из независимых множеств [ править ]

Число доминации независимости iγ ( G ) граф G является максимальной, по всем независимым множествам А из G , наималейшего множества доминирующего A . [5] Доминирующие подмножества вершин требуют потенциально меньше вершин , чем доминирующие все вершины, так iγ ( G ) & le  ; & gamma ( G ) для всех графов G .

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

Би-независимое доминирование номер iγi ( G ) графа G является максимальным, по всем независимых множеств А из G , наименьшего независимого множества доминирующих А . Для любого графа G выполняются следующие соотношения :

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

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

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

L-редукции [ править ]

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

От доминирующего набора до набора покрытия. Для графа G  = ( V ,  E ) с V  = {1, 2, ...,  n } постройте экземпляр покрытия множества ( U ,  S ) следующим образом: универсум U равен V , а семейство подмножеств S  = { S 1 , S 2 , ..., S п } такое , что S V состоит из вершины 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  = {1, 2, 5}, S 2  = {1, 2, 3, 5}, S 3  = {2, 3, 4, 6}, S 4  = {3, 4}, S 5  = {1, 2, 5, 6} и S 6  = {3, 5, 6}. В этом примере D  = {3, 5} является доминирующим множеством для G - это соответствует множеству покрытия C  = { S 3 ,  S 5 }. Например, вершина 4 ∈  Vдоминирует в вершине 3 ∈  D , а элемент 4 ∈  U содержится в множестве S 3  ∈  C .

От покрытия до доминирующего набора. Пусть ( S ,  U ) - пример задачи покрытия множеств с универсумом U и семейством подмножеств S  = { S i  :  i  ∈  I }; мы предполагаем, что U и индексное множество I не пересекаются. Построим граф G  = ( V ,  E ) следующим образом: множество вершин V  =  I  ∪  U , между каждой парой i есть ребро { i ,  j } ∈  E , j  ∈  I , а также существует ребро { 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 смежна с вершиной в 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}, S 1  = { a ,  b ,  c }, S 2  = { a ,  b }, S 3  = { b ,  c ,  d } и S 4  = { c ,  d ,  e }.
В этом примере C  = { S 1 ,  S 4 } - это обложка набора; это соответствует доминирующему множеству D  = {1, 4}.
D  = { , 3, 4} является еще одним доминирующим множеством для графа G . Учитывая , D , мы можем построить доминирующее множество Х  = {1, 3, 4} , который не больше , чем D , и которая представляет собой подмножество I . Доминирующее множество X соответствует покрытию множества C  = { S 1 ,  S 3 ,  S 4 }.

Особые случаи [ править ]

Если граф имеет максимальную степень Δ, то алгоритм жадного приближения находит O (log Δ) -приближение минимального доминирующего множества. Кроме того, пусть d g - мощность доминирующего множества, полученного с помощью жадной аппроксимации, тогда выполняется следующее соотношение , где N - количество узлов, а M - количество ребер в данном неориентированном графе. [9] Для фиксированного Δ это квалифицируется как доминирующий набор для членства в APX ; по сути, это APX-полный. [10]

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

Точные алгоритмы [ править ]

Минимальное доминирующее множество графа с n вершинами может быть найдено за время O (2 n n ) путем проверки всех подмножеств вершин. Fomin, Grandoni & Kratsch (2009) показывают, как найти минимальное доминирующее множество во времени O (1,5137 n ) и экспоненциальном пространстве, а также во времени O (1,5264 n ) и полиномиальном пространстве. Более быстрый алгоритм, использующий время O (1,5048 n ), был найден van Rooij, Nederlof & van Dijk (2009) , которые также показали, что количество минимальных доминирующих множеств может быть вычислено за это время. Количество минимальных доминирующих множеств не превосходит 1,7159 nи все такие множества можно перечислить за время O (1,7159 n ). [13]

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

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

С другой стороны, если входной граф плоский, проблема остается NP-сложной, но известен алгоритм с фиксированными параметрами. В самом деле, эта проблема имеет ядро размера линейного по к , [14] и эксплуатационные разы, которые экспоненту в √ K и кубические в п может быть получены путем применения динамического программирования к ветви-разложению ядра. [15] В более общем смысле, проблема доминирующего множества и многие варианты задачи являются решаемыми с фиксированными параметрами, если параметризованы как размером доминирующего множества, так и размером наименьшего запрещенного полного двудольного подграфа ; то есть проблема в FPT награфы без бикликов , очень общий класс разреженных графов, который включает плоские графы. [16]

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

Варианты [ править ]

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

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

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Garey & Johnson (1979) .
  2. ^ Hedetniemi & Laskar (1990) .
  3. ^ Аллан и Ласкар (1978) .
  4. ^ Faudree, Flandrin & Ryjáček (1997) .
  5. ^ a b Ахарони, Рон; Бергер, Эли; Зив, Ран (2007-05-01). «Независимые системы представителей в взвешенных графах». Combinatorica . 27 (3): 253–267. DOI : 10.1007 / s00493-007-2086-у . ISSN  1439-6912 . S2CID  43510417 .
  6. ^ a b Kann (1992) , стр. 108–109.
  7. ^ Эскофье и Paschos (2006) .
  8. ^ Raz & Сафра (1997) .
  9. ^ Parekh (1991) .
  10. ^ Papadimitriou & Yannakakis (1991) .
  11. ^ Crescenzi et al. (2000) .
  12. ^ Takamizawa, Nishizeki и Саито (1982) .
  13. ^ Фомин и др. (2008) .
  14. Перейти ↑ Alber, Fellows & Niedermeier (2004) .
  15. ^ Фомин & Thilikos (2006) .
  16. ^ Telle & Villanger (2012) .
  17. ^ Dehne et al. (2006) .
  18. ^ Klasing & Laforest (2004) .
  19. Перейти ↑ Förster (2013) .
  20. ^ Мешулам, Рой (2003-05-01). «Числа доминирования и гомология» . Журнал комбинаторной теории, Серия А . 102 (2): 321–330. DOI : 10.1016 / S0097-3165 (03) 00045-1 . ISSN 0097-3165 . 

Ссылки [ править ]

  • Альбер, Йохен; Товарищи, Майкл Р .; Нидермайер, Рольф (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.
  • Крещенци, Пьерлуиджи; Канн, Вигго; Халлдорссон, Магнус; Карпинский, Марек ; Woeginger, Gerhard (2000), «Минимальное доминирующее множество», Сборник проблем оптимизации NP CS1 maint: discouraged parameter (link).
  • Дене, Франк; Товарищи, Майкл; Фернау, Хеннинг; Прието, Елена; Розамонд, Фрэнсис (2006), «Неблокатор: параметризованная алгоритмика для минимального доминирующего множества» (PDF) , SOFSEM 2006: 32-я конференция по текущим тенденциям в теории и практике компьютерных наук, Мерин, Чешская Республика, 21-27 января 2006 г., Труды , Lecture Notes в области компьютерных наук, 3831 ., Springer, С. 237-245, DOI : 10.1007 / 11611257_21.
  • Эскофье, Бруно; Paschos, Vangelis Th. (2006), "Полнота в классах приближения за пределами APX", теоретической информатики , 359 (1-3): 369-377, DOI : 10.1016 / j.tcs.2006.05.023
  • Фодри, Ральф ; Фландрин, Эвелин; Ryjáček, Зденек (1997), "лапка свободной графики - опрос А", дискретной математики , 164 (1-3): 87-147, DOI : 10.1016 / S0012-365X (96) 00045-3 , МР  1432221.
  • Фомин, Федор В .; Грандони, Фабрицио; Kratsch, Дитер (2009), "Мера и захват подход к анализу точных алгоритмов", Журнал ACM , 56 (5): 25: 1-32, DOI : 10,1145 / 1552285,1552286 , S2CID  1186651.
  • Фомин, Федор В .; Грандони, Фабрицио; Пяткин, Артем; Степанов, Алексей (2008), "Комбинаторные оценки через меру и властвуй: Ограничительная минимальные наборы доминирующие и приложения", ACM Сделки по алгоритмам , 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. из десятого семинар по аналитической Algorithmics и комбинаторики ANALCO ., SIAM, С. 25-32, DOI : 10.1137 / 1.9781611973037.4 , ISBN 978-1-61197-254-2.
  • Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5, п. 190, проблема GT2.
  • Хедетниеми, СТ; Laskar, RC (1990), "Библиография по доминированию в графах и некоторые основные определения параметров доминирования", Дискретная математика , 86 (1-3): 257-277, DOI : 10.1016 / 0012-365X (90) 90365-O.
  • Канн, Вигго (1992), Об аппроксимируемости NP-полных задач оптимизации (PDF) . Кандидатская диссертация, Департамент численного анализа и вычислительной техники, Королевский технологический институт , СтокгольмCS1 maint: postscript (link).
  • Класинг, Ральф; Laforest, Christian (2004), "Результаты твердости и алгоритмы аппроксимации k-кортежей доминирования в графах", Письма об обработке информации , 89 (2): 75–83, DOI : 10.1016 / j.ipl.2003.10.004.
  • Papadimitriou, Christos H .; Yannakakis, Mihailis (1991), "оптимизация, аппроксимация, и сложности классы", журнал компьютерных и системных наук , 43 (3): 425-440, DOI : 10,1016 / 0022-0000 (91) 90023-X
  • Парех, Абхай К. (1991), «Анализ жадной эвристики для поиска малых доминирующих множеств в графах», Письма об обработке информации , 39 (5): 237–240, DOI : 10.1016 / 0020-0190 (91) 90021-9
  • Raz, R .; Safra, S. (1997), "Тест низкой степени вероятности ошибки субконстанты и характеристика PCP субконстанты вероятности ошибки NP", Proc. 29-й ежегодный симпозиум ACM по теории вычислений , ACM, стр. 475–484, DOI : 10.1145 / 258533.258641 , ISBN 0-89791-888-6, S2CID  15457604.
  • Takamizawa, K .; Нишизеки, Т .; Сайт, N. (1982), "Линейное время Вычислимость комбинаторных задач на последовательно-параллельных графах", Журнал ACM , 29 (3): 623-641, DOI : 10,1145 / 322326,322328 , S2CID  16082154.
  • Телле, Ян Арне; Вилланджер, Ингве (2012), «FPT-алгоритмы для доминирования в графах без бикликов», у Эпштейна, Лия; Ferragina, Паоло (ред.), Алгоритмы - ESA 2012: 20 Ежегодный европейский симпозиум, Любляна, Словения, 10-12 сентября, 2012, Труды , Lecture Notes в области компьютерных наук , 7501 ., Springer, С. 802-812, DOI : 10.1007 / 978-3-642-33090-2_69.
  • van Rooij, JMM; Nederlof, J .; Ван Дейк, TC (2009), "Включение / исключение встречает меру и победа: точные алгоритмы для подсчета доминирующих множеств", Proc. Семнадцатый ежегодный Европейский симпозиум по алгоритмам, ESA 2009 , Lecture Notes в области компьютерных наук, 5757 ., М., С. 554-565, DOI : 10.1007 / 978-3-642-04128-0_50 , ISBN 978-3-642-04127-3.

Дальнейшее чтение [ править ]

  • Grandoni, F. (2006), "Замечание о сложности минимального доминирующего множества", журнал дискретных алгоритмов , 4 (2): 209-214, CiteSeerX  10.1.1.108.3223 , DOI : 10.1016 / j.jda.2005.03 0,002.
  • Guha, S .; Khuller, S. (1998), "Приближенные алгоритмы для связных множеств господствующих" (PDF) , Algorithmica , 20 (4): 374-387, DOI : 10.1007 / PL00009201 , ЛВП : 1903/830 , S2CID  1249122.
  • Хейнс, Тереза ​​В .; Хедетниеми, Стивен; Слейтер, Питер (1998a), Основы доминирования в графах , Марсель Деккер, ISBN 0-8247-0033-3, OCLC  37903553.
  • Хейнс, Тереза ​​В .; Хедетниеми, Стивен; Слейтер, Питер (1998b), Доминирование в графах: продвинутые темы , Марсель Деккер, ISBN 0-8247-0034-1, OCLC  38201061.