Связное доминирующее множество: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 7: Строка 7:
Рассмотрим граф G = (V, E). Множество C множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется ''связным доминирующим множеством''. Связное доминирующее множество минимальной мощности называется ''минимальным связным доминирующим множеством'' (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <math>\rho\ H(\Delta\ )</math> для <math>\rho\ < 1</math>, за исключением случая <math>NP \subseteq DTIME(n^{O(lnln n)})</math>, где H – гармоническая функция, а <math>\Delta\ </math> – максимальная степень исходного графа [10].
Рассмотрим граф G = (V, E). Множество C множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется ''связным доминирующим множеством''. Связное доминирующее множество минимальной мощности называется ''минимальным связным доминирующим множеством'' (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <math>\rho\ H(\Delta\ )</math> для <math>\rho\ < 1</math>, за исключением случая <math>NP \subseteq DTIME(n^{O(lnln n)})</math>, где H – гармоническая функция, а <math>\Delta\ </math> – максимальная степень исходного графа [10].


Единичным диском называется диск с радиусом, равным единице. [[Граф единичных дисков]] ассоциирован с множеством единичных дисков на евклидовой плоскости. Каждая вершина является центром единичного диска. Между двумя вершинами u и v существует дуга в том и только том случае, если <math>|uv| \le 1</math>, где <math>|uv| \; </math> – евклидово расстояние между u и v. Это означает, что две вершины u и v связаны дугой в том и только том случае, если диск вершины u покрывает v, а диск v покрывает u.
Единичным диском называется диск с радиусом, равным единице. [[Граф единичных дисков]] ассоциирован с множеством единичных дисков на евклидовой плоскости. Каждая вершина является центром единичного диска. Между двумя вершинами u и v существует ребро в том и только том случае, если <math>|uv| \le 1</math>, где <math>|uv| \; </math> – евклидово расстояние между u и v. Это означает, что две вершины u и v связаны ребром в том и только том случае, если диск вершины u покрывает v, а диск v покрывает u.


Вычисление МСДМ для графа единичных дисков также является NP-полной задачей; однако можно построить неплохую аппроксимацию для ее решения; Чен и коллеги [5] представили для нее схему аппроксимации с полиномиальным временем исполнения.
Вычисление МСДМ для графа единичных дисков также является NP-полной задачей; однако можно построить неплохую аппроксимацию для ее решения; Чен и коллеги [5] представили для нее схему аппроксимации с полиномиальным временем исполнения.
4510

правок

Навигация