What is the translation of " MINIMUM DOMINATING " in Russian?

• минимального доминирующего
• минимальное доминирующее

Examples of using Minimum dominating in English and their translations into Russian

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

There are graph families in which a minimum maximal independent set is a minimum dominating set.
Существуют семейства графов, в которых минимальное наибольшее независимое множество является минимальным доминирующим множеством.

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

There exist a pair of polynomial-time L-reductions between the minimum dominating set problem and the set cover problem.
Существует пара L- приведений полиномиального времени между задачей минимального доминирующего множества и задачей о покрытии множества.

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

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

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

A graph is called domination perfect if it has a minimum dominating set that is independent, and if the same property holds in all of its induced subgraphs.
Граф называется совершенным графом доминирования, если он имеет минимальное доминирующее множество, являющееся независимым множеством вершин, и если тем же самым свойством обладают все порожденные подграфы.

In particular, an efficient α-approximation algorithm for set covering provides an efficient α-approximation algorithm for minimum dominating sets.
В частности, эффективный α- аппроксимационный алгоритм для покрытия множества дает эффективный α- аппроксимационный алгоритм для минимальных доминирующих множеств.

Fomin, Grandoni& Kratsch(2009) show how to find a minimum dominating set in time O(1.5137n) and exponential space, and in time O(1.5264n) and polynomial space.
Фомин, Грандони и Кратч показали, как найти минимальное доминирующее множество за время O( 1. 5137n), при использовании экспоненциальной памяти, и за время O( 1. 5264n), при использовании полиномиальной памяти.

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

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.
Минимальное доминирующее множество в графе не обязательно будет независимым, но размер минимального доминирующего множества всегда меньше либо равен размеру минимального наибольшего независимого множества, то есть γ( G)≤ iG.

For any graph G, its line graph L(G) is claw-free, and hence a minimum maximal independent set in L(G) is also a minimum dominating set in LG.
Для любого графа G его реберный граф L( G) является свободным от клешней, а потому минимальное наибольшее независимое множество в L( G) является также минимальным доминирующим множеством в LG.

A similar approach leads to improved exponential-time algorithms for the maximum cut and minimum dominating set problems in cubic graphs, and for several other NP-hard optimization problems.
Похожий подход ведет к улучшенным алгоритмам экспоненциального времени для задач максимального разреза и минимального доминирующего множества для кубических графов и для некоторых других NP- трудных оптимизационных задач.

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.
Кроме моделирования некоторых типов электрических цепей, эти графы представляют интерес в теории вычислительной сложности, поскольку много стандартных задач на графах решаются в линейное время на ОТП- графах, включая поиск максимального паросочетания, максимального независимого множества, минимального доминирующего множества и гамильтонова дополнения.

Moreover, the reductions preserve the approximation ratio: for any α, a polynomial-time α-approximation algorithm for minimum dominating sets would provide a polynomial-time α-approximation algorithm for the set cover problem and vice versa.
Более того, приведения сохраняют аппроксимационный коэффициент- для любого α, α- аппроксимирующий алгоритм полиномиального времени нахождения минимального доминирующих множеств обеспечил бы α- аппроксимирующий алгоритм полиномиального времени для задачи о покрытии множества, и наоборот.

A faster algorithm, using O(1.5048n) time was found by van Rooij, Nederlof& van Dijk(2009), who also show that the number of minimum dominating sets can be computed in this time.
Более быстрый алгоритм, работающий за время O( 1. 5048n), был найден фон Роем, Недерлофом и фон Дейком, которые показали, что число минимальных доминирующих множеств может быть вычислено за указанное время.

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.
Однако в контраст с более общими классами графов, поиск минимального доминирующего множества в графе без клешней обладает параметрической сложностью с фиксированными параметрами- задача может быть решена за время, полиномиально зависящее от размера графа и экспоненциально от размера доминирующего множества.

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.
Повторяя эти замены, мы достигнем доминирующего множества, не превосходящего D, так что, если начальное D- минимальное доминирующее множество, процесс закончится созданием равного по размеру независимого доминирующего множества.

This technique has given PTASs for the following problems: subgraph isomorphism, maximum independent set, minimum vertex cover, minimum dominating set, minimum edge dominating set, maximum triangle matching, and many others.
Эта техника дала ПСПВ для следующих задач: задача поиска изоморфного подграфа, задача о максимальном независимом множестве, задача о вершинном покрытии, минимальное доминирующее множество, минимальное доминирующее множество ребер многие другие.

While some basic problems such as maximum independent set, maximum clique, coloring and clique cover remain NP-complete for dually chordal graphs, some variants of the minimum dominating set problem and Steiner tree are efficiently solvable on dually chordal graphs but Independent Domination remains NP-complete.
В то время как основные задачи, такие как поиск максимального независимого множества, максимальной клики, раскраски и кликового покрытия остаются NP- полными для двойственных хордальных графов, некоторые варианты задачи о минимальном доминирующем множестве и дереве Штейнера эффективно решаются для двойственных хордальных графов но задача независимого доминирования остается NP- полной.

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

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

Therefore, finding minimum connected dominating sets is equivalent to finding spanning trees with the maximum possible number of leaves.
Таким образом, поиск минимальных связных доминирующих множеств эквивалентен поиску остовных деревьев с максимальным возможным числом листьев.

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

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.
Таким образом можно полагать, что задачу нахождения минимального связного доминирующего множества и задачу поиска остовного дерева с максимальным числом листьев нельзя решить за полиномиальное время.

Conversely, if we are given a minimum edge dominating set with k edges, we can construct a maximal matching with k edges in polynomial time.
И обратно, если задано минимальное реберное доминирующее множество с k ребрами, мы можем построить наибольшее паросочетание с k ребрами за полиномиальное время.

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

In sectors with a limited number of dominating producers the minimum number of units may be increased to five and more.
В случае секторов, в которых имеется несколько доминирующих производителей, минимальное число единиц может быть увеличено до пяти и более.