Связанный доминирующий набор - Connected dominating set

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

Определения

Связное доминирующее множество графа грамм это набор D вершин с двумя свойствами:

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

А минимальный связанный доминирующий набор графа грамм является связным доминирующим множеством с наименьшим возможным мощность среди всех связанных доминирующих множеств грамм. В связанный номер доминирования из грамм - количество вершин в минимальном связном доминирующем множестве.[1]

Любой остовное дерево Т графа грамм имеет не менее двух листьев, вершины которых имеют только одно ребро Т инцидент с ними. Остовное дерево с максимальным количеством листьев - это остовное дерево, которое имеет максимально возможное количество листьев среди всех остовных деревьев грамм. В максимальное количество створок из грамм - количество листьев в остовном дереве с максимальным количеством листьев.[2]

Комплементарность

Если d это связанное число доминирования п-вершинный граф грамм, куда п> 2, и л - его максимальное количество листьев, тогда три величины d, л, и п подчиняться простому уравнению

[3]

Если D связное доминирующее множество, то существует остовное дерево в грамм листья которого включают в себя все вершины, не входящие в D: сформировать остовное дерево подграфа, индуцированного D, вместе с ребрами, соединяющими каждую оставшуюся вершину v это не в D к соседу v в D. Это показывает, что л ≥ п − d.

В обратном направлении, если Т любое остовное дерево в грамм, то вершины Т которые не являются листьями, образуют связанный доминирующий набор грамм. Это показывает, что п − л ≥ d. Объединение этих двух неравенств доказывает равенство п = d + л.

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

Алгоритмы

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

Если рассматривать с точки зрения алгоритмов аппроксимации, связное доминирование и максимальное листовое остовное дерево - это не одно и то же: аппроксимация одного с точностью до заданного. коэффициент аппроксимации это не то же самое, что приближение другого к тому же отношению. Существует приближение для минимального связного доминирующего множества, которое достигает коэффициента 2 ln Δ + O (1), где Δ - максимальная степень вершины в G.[4]Задача максимального листового остовного дерева МАКС-СНП трудно, подразумевая, что нет схема аппроксимации полиномиальным временем похоже.[5] Однако за полиномиальное время его можно аппроксимировать с точностью до 2 раз.[6]

Обе проблемы можно решить, п-вершинные графы, во времени О(1.9п).[7] Максимальная проблема с листьями управляемый с фиксированными параметрами, что означает, что она может быть решена за время, экспоненциальное по количеству листьев, но только полиномиальное по размеру входного графа. В значение клама Количество этих алгоритмов (интуитивно понятно, что количество листов, до которых проблема может быть решена в разумные сроки) постепенно увеличивалось по мере улучшения алгоритмов решения проблемы примерно до 37,[8] и было предложено достичь не менее 50.[9]

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

Приложения

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

Максимальное количество створок было использовано при разработке управляемый с фиксированными параметрами алгоритмы: несколько NP-сложных задач оптимизации могут быть решены за полиномиальное время для графов с ограниченным максимальным числом листьев.[2]

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

  • Универсальная вершина, вершина, которая (когда она существует) дает минимальное связное доминирующее множество размера один

Рекомендации

  1. ^ Sampathkumar, E .; Валикар, HB (1979), "Число связного доминирования графа", J. Math. Phys. Наука, 13 (6): 607–613.
  2. ^ а б Товарищи, Майкл; Локштанов Даниил; Мишра, Нилдхара; Мних, Матиас; Розамонд, Фрэнсис; Саураб, Сакет (2009), "Экология сложности параметров: иллюстрация с использованием ограниченного максимального числа листьев", Теория вычислительных систем, 45 (4): 822–848, Дои:10.1007 / s00224-009-9167-9.
  3. ^ Дуглас, Роберт Дж. (1992), "NP-полнота и остовные деревья с ограничением степени", Дискретная математика, 105 (1–3): 41–47, Дои:10.1016 / 0012-365X (92) 90130-8.
  4. ^ Guha, S .; Хуллер, С. (1998), "Алгоритмы приближения для связных доминирующих множеств", Алгоритмика, 20 (4): 374–387, Дои:10.1007 / PL00009201, HDL:1903/830.
  5. ^ Galbiati, G .; Maffioli, F .; Морзенти, А. (1994), "Краткое замечание об аппроксимируемости задачи о максимальном остовном дереве листьев", Письма об обработке информации, 52 (1): 45–49, Дои:10.1016/0020-0190(94)90139-2.
  6. ^ Солис-Оба, Роберто (1998), «2-приближенный алгоритм для поиска остовного дерева с максимальным числом листьев», Proc. 6-й Европейский симпозиум по алгоритмам (ESA'98), Конспект лекций по информатике, 1461, Springer-Verlag, стр. 441–452, Дои:10.1007/3-540-68530-8_37, HDL:11858 / 00-001M-0000-0014-7BD6-0.
  7. ^ Фернау, Хеннинг; Кнейс, Иоахим; Крач, Дитер; Лангер, Александр; Лидлофф, Матье; Райбл, Дэниел; Россманит, Питер (2011), "Точный алгоритм решения проблемы максимального листового остовного дерева", Теоретическая информатика, 412 (45): 6290–6302, Дои:10.1016 / j.tcs.2011.07.011, МИСТЕР  2883043.
  8. ^ Бинкеле-Райбл, Даниэль; Фернау, Хеннинг (2014), "Параметризованный анализ меры и преодоления для поиска k-лист остовного дерева в неориентированном графе ", Дискретная математика и теоретическая информатика, 16 (1): 179–200, МИСТЕР  3188035.
  9. ^ Товарищи, Майкл Р.; Маккартин, Кэтрин; Розамонд, Фрэнсис А .; Стеге, Ульрике (2000), "Координированные ядра и каталитическое восстановление: улучшенный алгоритм FPT для максимального листового остовного дерева и других проблем", FST-TCS 2000: Основы программных технологий и теоретической информатики, Конспект лекций по вычисл. Наук, 1974, Springer, Berlin, pp. 240–251, Дои:10.1007/3-540-44450-5_19, МИСТЕР  1850108.
  10. ^ Уэно, Шуичи; Кадзитани, Йоджи; Гото, Шинья (1988), "О неразрывной проблеме независимого множества и задаче о множестве обратной связи для графов, у которых степень вершин не превышает трех", Труды Первой японской конференции по теории графов и приложениям (Хаконэ, 1986), Дискретная математика, 72 (1–3): 355–360, Дои:10.1016 / 0012-365X (88) 90226-9, МИСТЕР  0975556
  11. ^ Wu, J .; Ли, Х. (1999), "О вычислении доминирующего связного множества для эффективной маршрутизации в специальных беспроводных сетях", Труды 3-го международного семинара по дискретным алгоритмам и методам мобильных вычислений и коммуникаций, ACM, стр. 7–14, Дои:10.1145/313239.313261.