Связное доминирующее множество
В теории графов связное доминирующее множество и остовное дерево с максимальным листом представляют собой две тесно связанные структуры, определенные на неориентированном графе .
Определения
[ редактировать ]Связным доминирующим множеством графа G называется множество D вершин, обладающее двумя свойствами:
- Любой узел в D может достичь любого другого узла в D по пути, который полностью находится D. внутри То есть D индуцирует связный подграф G .
- Каждая вершина в G либо принадлежит D либо смежна с вершиной в D. , То есть D является доминирующим множеством G .
Минимальным связным доминирующим множеством графа G называется связное доминирующее множество с наименьшей возможной мощностью среди всех связных доминирующих множеств графа G . Число связного доминирования графа G — это количество вершин в минимальном связном доминирующем множестве. [1]
Любое остовное дерево T графа G имеет как минимум два листа, вершины, которым только одно ребро из T. инцидентно Опорное дерево с максимальным количеством листьев — это остовное дерево, которое имеет максимально возможное количество листьев среди всех остовных деревьев G . Максимальное листьев G количество — это количество листьев в максимальном остовном дереве. [2]
Дополнительность
[ редактировать ]Если d — связное число доминирования n -вершинного графа G , где n > 2 , а l — его максимальное число листьев, то три величины d , l и n подчиняются простому уравнению
Если D существует остовное дерево — связное доминирующее множество, то в G , листья которого включают все вершины, которых нет в D : образуют остовное дерево подграфа, индуцированного D , вместе с ребрами, соединяющими каждую оставшуюся вершину v , которая не находится в D соседу v в D . Это показывает, что l ≥ n - d .
В другом направлении, если T — любое остовное дерево в G , то вершины T которые не являются листьями, образуют связное доминирующее множество G. , Это показывает, что n - l ≥ d . Соединение этих двух неравенств вместе доказывает равенство n = d + l .
Следовательно, в любом графе сумма числа доминирования связности и максимального числа листьев равна общему количеству вершин.С вычислительной точки зрения это означает, что определение связанного числа доминирования так же сложно, как и определение максимального числа листьев.
Алгоритмы
[ редактировать ]является NP-полной проверка существования связного доминирующего множества размером меньше заданного порога или, что то же самое, проверка существования остовного дерева хотя бы с заданным количеством листьев. Поэтому считается, что задача минимального связного доминирующего множества и задача максимального связного дерева не могут быть решены за полиномиальное время.
Если рассматривать с точки зрения алгоритмов аппроксимации, связанное доминирование и остовное дерево с максимальным числом листьев — это не одно и то же: аппроксимация одного с точностью до заданного коэффициента аппроксимации — это не то же самое, что аппроксимация другого с тем же коэффициентом.Существует приближение минимального связного доминирующего множества, которое достигает коэффициента 2 ln Δ + O(1) , где Δ — максимальная степень вершины в G. [4] Задача о максимальном листовом связующем дереве сложна MAX-SNP , что означает, что схема аппроксимации с полиномиальным временем невозможна. [5] Однако его можно аппроксимировать с точностью до 2 раз за полиномиальное время. [6]
Обе задачи могут быть решены на с n графах вершинами за время O (1,9 н ) . [7] Проблема максимального листа является управляемой с фиксированным параметром , что означает, что ее можно решить за время, экспоненциальное по количеству листьев, но только полиномиальное по размеру входного графа. Значение klam этих алгоритмов (интуитивно, количество листьев, до которых задача может быть решена за разумный промежуток времени) постепенно увеличивалось по мере совершенствования алгоритмов решения задачи примерно до 37. [8] и было высказано предположение, что по крайней мере 50 должно быть достижимо. [9]
В графах максимальной степени три связное доминирующее множество и дополнительная к нему проблема остовного дерева с максимальным листом могут быть решены за полиномиальное время , преобразуя их в экземпляр проблемы четности матроидов для линейных матроидов . [10]
Приложения
[ редактировать ]Связанные доминирующие множества полезны при расчете маршрутизации для мобильных одноранговых сетей . В этом приложении небольшой подключенный доминирующий набор используется в качестве магистрали для связи, а узлы, не входящие в этот набор, взаимодействуют, передавая сообщения через соседей, которые входят в этот набор. [11]
Максимальное число листьев использовалось при разработке с фиксированным параметром управляемых алгоритмов : несколько NP-сложных задач оптимизации могут быть решены за полиномиальное время для графов с ограниченным максимальным числом листьев. [2]
См. также
[ редактировать ]- Универсальная вершина — вершина, которая (если она существует) дает минимальное связное доминирующее множество размера один.
Ссылки
[ редактировать ]- ^ Сампаткумар, Э.; Валикар, Х.Б. (1979), «Связное доминантное число графа», J. Math. Физ. Sci , 13 (6): 607–613 .
- ^ Перейти обратно: а б Ребята, Майкл; Локштанов Даниил; Мишра, Нильдхара; Мних, Матиас; Розамонд, Фрэнсис; Саураб, Сакет (2009), «Экология сложности параметров: иллюстрация с использованием ограниченного максимального числа листов», Theory of Computing Systems , 45 (4): 822–848, doi : 10.1007/s00224-009-9167-9 , S2CID 4053586 .
- ^ Дуглас, Роберт Дж. (1992), «NP-полнота и остовные деревья с ограниченной степенью», Discrete Mathematics , 105 (1–3): 41–47, doi : 10.1016/0012-365X(92)90130-8 .
- ^ Гуха, С.; Хуллер, С. (1998), «Алгоритмы аппроксимации связных доминирующих множеств», Algorithmica , 20 (4): 374–387, doi : 10.1007/PL00009201 , hdl : 1903/830 , S2CID 263230631 .
- ^ Гальбиати, Г.; Маффиоли, Ф.; Морзенти, А. (1994), «Краткая заметка об аппроксимируемости проблемы максимального количества листьев», Information Processing Letters , 52 (1): 45–49, doi : 10.1016/0020-0190(94)90139-2 .
- ^ Солис-Оба, Роберто (1998), "2-приближенный алгоритм поиска остовного дерева с максимальным количеством листьев", Proc. 6-й Европейский симпозиум по алгоритмам (ESA'98) , Конспекты лекций по информатике, том. 1461, Springer-Verlag, стр. 441–452, doi : 10.1007/3-540-68530-8_37 , hdl : 11858/00-001M-0000-0014-7BD6-0 , ISBN 978-3-540-64848-2 .
- ^ Фернау, Хеннинг; Кнейс, Иоахим; Крач, Дитер; Лангер, Александр; Лидлофф, Матье; Райбл, Дэниел; Россманит, Питер (2011), «Точный алгоритм решения проблемы остовного дерева с максимальным числом листьев», Theoretical Computer Science , 412 (45): 6290–6302, doi : 10.1016/j.tcs.2011.07.011 , MR 2883043 .
- ^ Бинкеле-Райбл, Даниэль; Фернау, Хеннинг (2014), «Параметризованный анализ «меряй и властвуй» для поиска связующего дерева с k -листом в неориентированном графе», Discrete Mathematics & Theoretical Computer Science , 16 (1): 179–200, MR 3188035 .
- ^ Товарищи, Майкл Р .; Маккартин, Кэтрин; Розамонд, Фрэнсис А.; Стеге, Ульрике (2000), «Координированные ядра и каталитические сокращения: улучшенный алгоритм FPT для максимального листового связующего дерева и других проблем», FST-TCS 2000: Основы программных технологий и теоретической информатики , Конспекты лекций по вычислительной технике. наук., вып. 1974, Springer, Берлин, стр. 240–251, номер документа : 10.1007/3-540-44450-5_19 , ISBN. 978-3-540-41413-1 , МР 1850108 .
- ^ Уэно, Шуичи; Кадзитани, Йоджи; Гото, Шинья (1988), «О проблеме неразделяющегося независимого множества и проблеме множества с обратной связью для графов, степень вершины которых не превышает трех», Труды Первой японской конференции по теории графов и приложениям (Хаконэ, 1986), Дискретная математика , 72 (1–3): 355–360, doi : 10.1016/0012-365X(88)90226-9 , MR 0975556
- ^ Ву, Дж.; Ли, Х. (1999), «О вычислении связанного доминирующего набора для эффективной маршрутизации в одноранговых беспроводных сетях», Труды 3-го международного семинара по дискретным алгоритмам и методам мобильных вычислений и коммуникаций , ACM, стр. 7–14, doi : 10.1145/313239.313261 , ISBN 1-58113-174-7 , S2CID 59969437 .