Доминирующий набор
В теории графов для доминирующим множеством графа G является подмножество D его вершин, такое, что любая вершина находится в D или имеет соседа в D. G Число доминирования γ( G ) — это количество вершин в наименьшем доминирующем множестве для G .
Проблема доминирующего множества касается проверки того, является ли γ( G ) ⩽ K для данного графа G и входных данных K ; это классическая NP-полная задача решения в теории сложности вычислений . [1] Поэтому считается, что не может быть алгоритма , который мог бы вычислить γ( G ) для всех графов G. эффективного Однако существуют эффективные алгоритмы аппроксимации , а также эффективные точные алгоритмы для определенных классов графов.
Доминирующие множества представляют практический интерес в нескольких областях. В беспроводных сетях доминирующие наборы используются для поиска эффективных маршрутов в одноранговых мобильных сетях. Они также использовались при обобщении документов и при проектировании безопасных систем для электрических сетей .
Формальное определение
[ редактировать ]Учитывая неориентированный граф G = ( V , E ) , подмножество вершин называется доминирующим множеством, если для каждой вершины , есть вершина такой, что .
Каждый граф имеет хотя бы одно доминирующее множество: если множество всех вершин, то по определению D является доминирующим множеством, так как не существует вершины . Более интересная задача — найти небольшие доминирующие множества. Число доминирования G : определяется как .
Варианты
[ редактировать ]— Связное доминирующее множество это доминирующее множество, которое также связно . Если S — связное доминирующее множество, можно сформировать остовное дерево G , в котором S образует множество нелистовых вершин дерева; и наоборот, если T — любое остовное дерево в графе с более чем двумя вершинами, нелистовые вершины T образуют связное доминирующее множество. Следовательно, поиск минимального связного доминирующего множества эквивалентен поиску остовного дерева с максимально возможным числом листьев.
Полный доминирующий набор (или сильно доминирующий набор ) — это набор вершин, такой, что все вершины в графе, включая сами вершины в доминирующем множестве, имеют соседа в доминирующем множестве. [2] То есть: для каждой вершины , есть вершина такой, что . На рисунке (c) выше показано доминирующее множество, которое представляет собой связное доминирующее множество и полное доминирующее множество; примеры на рисунках (a) и (b) не являются ни тем, ни другим. В отличие от простого доминирующего множества, полное доминирующее множество может не существовать. Например, граф с одной или несколькими вершинами и без ребер не имеет полного доминирующего множества. Число сильного доминирования G : определяется как ; очевидно, .
Доминирующее множество ребер — это множество ребер (пар вершин), объединение которых является доминирующим множеством; такого множества может не существовать (например, его не имеет граф с одной или несколькими вершинами и без ребер). Если оно существует, то объединение всех его ребер является сильно доминирующим множеством. Следовательно, наименьший размер множества с доминирующим ребром не менее .
Напротив, набор с доминированием ребер - это набор 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 — двойной звездчатый граф , состоящий из вершин , где п , q > 1 . Ребра G определяются следующим образом: каждое xi a смежно с b , a смежно с b , а смежно с каждым y j . Тогда γ( G ) = 2, поскольку { a , b } — наименьшее доминирующее множество. Если p ≤ q , то я ( G ) = p + 1, поскольку — наименьшее доминирующее множество, которое также является независимым (это наименьшее максимальное независимое множество).
Существуют семейства графов, в которых γ( 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 является максимальным среди всех независимых множеств из G наименьшего множества, доминирующего над A. 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 :
История
[ редактировать ]Проблема доминирования изучалась с 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 1 , S 2 , ..., 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 = {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 , j } ∈ E , между каждой парой i , j ∈ I , а также существует ребро { я , ты } для каждого я € 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 1 = { a , b , c }, S 2 = { а , б }, S3 d { б , с , d } и S4 , = { с , } = е .
- В этом примере C = { S 1 , S 4 } является покрытием множества; это соответствует доминирующему множеству D = {1, 4}.
- D = { a , 3, 4} еще одно доминирующее множество графа G. — Учитывая D , мы можем построить доминирующее множество X = {1, 3, 4}, которое не больше D является подмножеством I. и которое Доминирующему множеству X соответствует покрытие множества C = { S 1 , S 3 , S 4 }.
Особые случаи
[ редактировать ]Если граф имеет максимальную степень Δ, то жадный алгоритм аппроксимации находит O (log Δ) -аппроксимацию минимального доминирующего множества. Кроме того, пусть d g — мощность доминирующего множества, полученная с использованием жадной аппроксимации, тогда справедливо следующее соотношение: , где N — количество узлов, а M — количество ребер в данном неориентированном графе. [13] Для фиксированного Δ это квалифицируется как доминирующий набор для в APX членства ; фактически, он APX-полный. [14]
Задача допускает схему аппроксимации полиномиального времени (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 О(1) для любой функции f существует, если W-иерархия не схлопывается до FPT=W[2].
С другой стороны, если входной граф является плоским, задача остается NP-сложной, но алгоритм с фиксированными параметрами известен. Фактически, задача имеет ядро линейного по k размера : [18] а время работы, экспоненциальное по √ k и кубическое по n, может быть получено путем применения динамического программирования к ветвящемуся разложению ядра. [19] В более общем смысле, проблема доминирующего набора и многие варианты проблемы решаются с фиксированным параметром, если они параметризованы как размером доминирующего набора, так и размером наименьшего запрещенного полного двудольного подграфа ; то есть проблема заключается в FPT на графах без биклик , очень общем классе разреженных графов, включающем планарные графы. [20]
Дополнительный набор к доминирующему множеству, неблокирующий , может быть найден с помощью алгоритма с фиксированными параметрами на любом графе. [21]
См. также
[ редактировать ]- Гипотеза Визинга - связывает число доминирования декартова произведения графов с числом доминирования его сомножителей.
- Установить проблему с обложкой
- Номер бондажа
- Неблокирующий – дополнение доминирующего множества.
Примечания
[ редактировать ]- ^ Гэри и Джонсон (1979) .
- ^ Вест (2001) , Раздел 3.1.
- ^ Класинг и Лафорест (2004) .
- ^ Фёрстер (2013) .
- ^ Мешулам, Рой (1 мая 2003 г.). «Числа доминирования и гомологии» . Журнал комбинаторной теории, серия А. 102 (2): 321–330. дои : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 .
- ^ Аллан и Ласкар (1978) .
- ^ Фаудри, Фландрин и Риячек (1997) .
- ^ Jump up to: а б Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах». Комбинаторика . 27 (3): 253–267. дои : 10.1007/s00493-007-2086-y . ISSN 1439-6912 . S2CID 43510417 .
- ^ Хедетниеми и Ласкар (1990) .
- ^ Jump up to: а б Джан (1992) , стр. 108–109.
- ^ Эскофье и Пашос (2006) .
- ^ Raz & Safra (1997) .
- ^ Парех (1991) .
- ^ Пападимитриу и Яннакакис (1991) .
- ^ Крещенци и др. (2000) .
- ^ Такамизава, Нисидзеки и Сайто (1982) .
- ^ Fomin et al. (2008) .
- ^ Альбер, Fellows & Niedermeier (2004) .
- ^ Фомин и Тиликос (2006) .
- ^ Телле и Вилланджер (2012) .
- ^ Дене и др. (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, doi : 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: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, номер документа : 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 .