What does dominating set mean?
Definitions for dominating set
dom·i·nat·ing set
This dictionary definitions page includes all the possible meanings, example usage and translations of the word dominating set.
Did you actually mean day-and-night?
Wiktionary
dominating setnoun
A set of vertices of a graph, such that each vertex in that graph is either in that set or adjacent to some vertex in that set.
Wikipedia
Dominating set
In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbor in D. The domination number γ(G) is the number of vertices in a smallest dominating set for G. The dominating set problem concerns testing whether γ(G) ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory. Therefore it is believed that there may be no efficient algorithm that can compute γ(G) for all graphs G. However, there are efficient approximation algorithms, as well as efficient exact algorithms for certain graph classes. Dominating sets are of practical interest in several areas. In wireless networking, dominating sets are used to find efficient routes within ad-hoc mobile networks. They have also been used in document summarization, and in designing secure systems for electrical grids.
Freebase
Dominating set
In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number γ is the number of vertices in a smallest dominating set for G. The dominating set problem concerns testing whether γ ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory. Therefore it is believed that there is no efficient algorithm that finds a smallest dominating set for a given graph. Figures – on the right show three examples of dominating sets for a graph. In each example, each white vertex is adjacent to at least one red vertex, and it is said that the white vertex is dominated by the red vertex. The domination number of this graph is 2: the examples and 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.
Numerology
Chaldean Numerology
The numerical value of dominating set in Chaldean Numerology is: 2
Pythagorean Numerology
The numerical value of dominating set in Pythagorean Numerology is: 6
Translations for dominating set
From our Multilingual Translation Dictionary
- dominierende MengeGerman
Get even more translations for dominating set »
Translation
Find a translation for the dominating set definition in other languages:
Select another language:
- - Select -
- 简体中文 (Chinese - Simplified)
- 繁體中文 (Chinese - Traditional)
- Español (Spanish)
- Esperanto (Esperanto)
- 日本語 (Japanese)
- Português (Portuguese)
- Deutsch (German)
- العربية (Arabic)
- Français (French)
- Русский (Russian)
- ಕನ್ನಡ (Kannada)
- 한국어 (Korean)
- עברית (Hebrew)
- Gaeilge (Irish)
- Українська (Ukrainian)
- اردو (Urdu)
- Magyar (Hungarian)
- मानक हिन्दी (Hindi)
- Indonesia (Indonesian)
- Italiano (Italian)
- தமிழ் (Tamil)
- Türkçe (Turkish)
- తెలుగు (Telugu)
- ภาษาไทย (Thai)
- Tiếng Việt (Vietnamese)
- Čeština (Czech)
- Polski (Polish)
- Bahasa Indonesia (Indonesian)
- Românește (Romanian)
- Nederlands (Dutch)
- Ελληνικά (Greek)
- Latinum (Latin)
- Svenska (Swedish)
- Dansk (Danish)
- Suomi (Finnish)
- فارسی (Persian)
- ייִדיש (Yiddish)
- հայերեն (Armenian)
- Norsk (Norwegian)
- English (English)
Word of the Day
Would you like us to send you a FREE new word definition delivered to your inbox daily?
Citation
Use the citation below to add this definition to your bibliography:
Style:MLAChicagoAPA
"dominating set." Definitions.net. STANDS4 LLC, 2023. Web. 29 Mar. 2023. <https://www.definitions.net/definition/dominating+set>.
Discuss these dominating set definitions with the community:
Report Comment
We're doing our best to make sure our content is useful, accurate and safe.
If by any chance you spot an inappropriate comment while navigating through our website please use this form to let us know, and we'll take care of it shortly.
Attachment
You need to be logged in to favorite.
Log In