Sta znaci na Engleskom ДОМИНИРУЮЩЕГО МНОЖЕСТВА - prevod na Енглеском

• dominating set

Примери коришћења Доминирующего множества на Руском и њихови преводи на Енглески

Поиск доминирующего множества размера k играет центральную роль в теории параметрической сложности.
Finding a dominating set of size k plays a central role in the theory of parameterized complexity.

Log n- аппроксимация минимального k- кортежного доминирующего множества может быть найден за полиномиальное время.
An(1+log n)-approximation of a minimum k-tuple dominating set can be found in polynomial time.

Некоторые формы задачи о картинной галерее можно интерпретировать как поиск доминирующего множества в графе видимости.
Certain forms of the art gallery problem may be interpreted as finding a dominating set in a visibility graph.

Более того, размер наименьшего доминирующего множества ребер равен размеру наименьшего максимального паросочетания.
Furthermore, the size of a minimum edge dominating set equals the size of a minimum maximal matching.

Если граф имеет максимальную степень Δ, то жадный аппроксимационный алгоритм находит O( log Δ)- аппроксимацию минимального доминирующего множества.
If the graph has maximum degree Δ, then the greedy approximation algorithm finds an O(log Δ)-approximation of a minimum dominating set.

Отсюда- размер минимального доминирующего множества для G равен размеру минимального покрытия множества для U, S.
Hence the size of a minimum dominating set for G equals the size of a minimum set cover for U, S.

Несмотря на свойство совершенного доминирования, определение размера минимального доминирующего множества в графе без клешней является NP- трудной задачей.
Despite this domination perfectness property, it is NP-hard to determine the size of the minimum dominating set in a claw-free graph.

В эти задачи входят поиски доминирующего множества, наименьшего связного доминирующего множества и наименьшего тотального доминирующего множества.
These include the minimum dominating set, minimum connected dominating set, and minimum total dominating set problems.

Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна задаче нахождения минимального реберного доминирующего множества.
Therefore, the problem of finding a minimum maximal matching is essentially equal to the problem of finding a minimum edge dominating set.

Таким образом можно полагать, что задачу нахождения минимального связного доминирующего множества и задачу поиска остовного дерева с максимальным числом листьев нельзя решить за полиномиальное время.
Therefore, it is believed that the minimum connected dominating set problem and the maximum leaf spanning tree problem cannot be solved in polynomial time.

К ним принадлежат задачи поиска минимального вершинного покрытия, максимального независимого множества, минимального доминирующего множества и максимального разреза.
These include the problems of finding a minimum vertex cover, maximum independent set, minimum dominating set, and maximum cut.

Число независимого доминирования i( G) графа G- это размер наименьшего независимого доминирующего множества или, эквивалентно, минимальный размер наибольших независимых множеств..
The independent domination number i(G) of a graph G is the size of the smallest independent dominating set or, equivalently, the size of the smallest maximal independent set..

На рисунках( a) и( b) представлены примеры наименьших доминирующих множеств ребер можно проверить, что для данного графа не существует доминирующего множества из двух ребер.
Figures(a) and(b) are examples of minimum edge dominating sets it can be checked that there is no edge dominating set of size 2 for this graph.

Минимальное доминирующее множество в графе не обязательно будет независимым, но размер минимального доминирующего множества всегда меньше либо равен размеру минимального наибольшего независимого множества, то есть γ( G)≤ iG.
The minimum dominating set in a graph will not necessarily be independent, but the size of a minimum dominating set is always less than or equal to the size of a minimum maximal independent set, that is, γ(G)≤ iG.

Определение, существует ли доминирующее множество ребер заданного размера для заданного графа, является NP- полной задачей а потому нахождение наименьшего доминирующего множества ребер является NP- трудной задачей.
Determining whether there is an edge dominating set of a given size for a given graph is an NP-complete problem and therefore finding a minimum edge dominating set is an NP-hard problem.

Повторяя эти замены, мы достигнем доминирующего множества, не превосходящего D, так что, если начальное D- минимальное доминирующее множество, процесс закончится созданием равного по размеру независимого доминирующего множества.
By repeating this replacement process one eventually reaches a dominating set no larger than D, so in particular when the starting set D is a minimum dominating set this process forms an equally small independent dominating set.

Доминирующее число этого графа равно 2- примеры( b) и( c) показывают, что существует доминирующее множество с 2 вершинами, и можно проверить, что для данного графа не существует доминирующего множества лишь с одной вершиной.
The domination number of this graph is 2: the examples(b) and(c) show that there is a dominating set with 2 vertices, and it can be checked that there is no dominating set with only 1 vertex for this graph.

Также пусть dg является мощностью доминирующего множества, полученного с помощью жадного аппроксимационного алгоритма, тогда выполняется следующее отношение: dg≤ N+ 1- 2 M+ 1{\ displaystyle{\ sqrt{ 2M+ 1}}}, где N- число узлов, а M- число ребер в заданном неориентированном графе.
Also, let dg be the cardinality of dominating set obtained using greedy approximation then following relation holds, d g≤ N+ 1- 2 M+ 1{\displaystyle d_{g}\leq N+1-{\sqrt{2M+1}}}, where N is number of nodes and M is number of edges in given undirected graph.

Если каждая вершина этой клики уже доминируется, по крайней мере, одним членом множества D, то v может быть удалена с порождением меньшего независимого доминирующего множества.
If every vertex in this clique is already dominated by at least one other member of D, then v can be removed producing a smaller independent dominating set, and otherwise v can be replaced by one of the undominated vertices in its clique producing a dominating set with fewer adjacencies.

Однако в контраст с более общими классами графов, поиск минимального доминирующего множества в графе без клешней обладает параметрической сложностью с фиксированными параметрами- задача может быть решена за время, полиномиально зависящее от размера графа и экспоненциально от размера доминирующего множества.
However, in contrast to the situation for more general classes of graphs, finding the minimum dominating set or the minimum connected dominating set in a claw-free graph is fixed-parameter tractable: it can be solved in time bounded by a polynomial in the size of the graph multiplied by an exponential function of the dominating set size.

Кроме моделирования некоторых типов электрических цепей, эти графы представляют интерес в теории вычислительной сложности, поскольку много стандартных задач на графах решаются в линейное время на ОТП- графах, включая поиск максимального паросочетания, максимального независимого множества, минимального доминирующего множества и гамильтонова дополнения.
Besides being a model of certain types of electric networks, these graphs are of interest in computational complexity theory, because a number of standard graph problems are solvable in linear time on SPGs, including finding of the maximum matching, maximum independent set, minimum dominating set and Hamiltonian completion.

Наименьшее доминирующее множество ребер( оптимизационная версия)- задача GT3 в Приложении B стр. 370.
Minimum edge dominating set(optimisation version) is the problem GT3 in Appendix B page 370.

Конфигурация охранников должна после каждой атаки и движения охранника образовывать доминирующее множество.
The configuration of guards after each attack must induce a dominating set.

Те же результаты верны для многих вариантов задачи о доминирующем множестве.
Similar results are true for many variations of the dominating set problem.

Любое максимальное паросочетание всегда является реберным доминирующим множеством.
Any maximal matching is always an edge dominating set.

Рисунки( a)-( c) справа показывают три примера доминирующих множеств графа.
Figures(a)-(c) on the right show three examples of dominating sets for a graph.

Имеется множество статей о связном доминирующем множестве.
There has been much work on connected dominating sets.

Число доминирования графа- это минимальный размер множества среди всех доминирующих множеств.
The domination number of a graph is the minimum cardinality among all dominating sets.

Более того, существует простой алгоритм, который отображает доминирующее множество в покрытие множества того же размера, и наоборот.
Furthermore, there is a simple algorithm that maps a dominating set to a set cover of the same size and vice versa.

Минимальное доминирующее множество графа с n вершинами может быть найдено за время O( 2nn) путем просмотра всех подмножеств вершин.
A minimum dominating set of an n-vertex graph can be found in time O(2nn) by inspecting all vertex subsets.