Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Dominating_set> ?p ?o. }
Showing items 1 to 39 of
39
with 100 items per page.
- Dominating_set abstract "In graph theory, a dominating set for a graph G = (V, E) 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 γ(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 (Garey & Johnson 1979). Therefore it is believed that there is no efficient algorithm that finds a smallest dominating set for a given graph.Figures (a)–(c) 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 (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.".
- Dominating_set thumbnail Dominating-set.svg?width=300.
- Dominating_set wikiPageExternalLink DSP.
- Dominating_set wikiPageExternalLink phdthesis.pdf.
- Dominating_set wikiPageExternalLink node11.html.
- Dominating_set wikiPageID "1747972".
- Dominating_set wikiPageRevisionID "569569420".
- Dominating_set hasPhotoCollection Dominating_set.
- Dominating_set subject Category:Computational_problems_in_graph_theory.
- Dominating_set subject Category:Graph_theory_objects.
- Dominating_set subject Category:NP-complete_problems.
- Dominating_set type Abstraction100002137.
- Dominating_set type Attribute100024264.
- Dominating_set type ComputationalProblemsInGraphTheory.
- Dominating_set type Condition113920835.
- Dominating_set type Difficulty114408086.
- Dominating_set type NP-completeProblems.
- Dominating_set type Problem114410605.
- Dominating_set type State100024720.
- Dominating_set comment "In graph theory, a dominating set for a graph G = (V, E) 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 γ(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 (Garey & Johnson 1979).".
- Dominating_set label "Conjunto dominante".
- Dominating_set label "Dominating set".
- Dominating_set label "Dominerende verzameling".
- Dominating_set label "Ensemble dominant".
- Dominating_set label "Zbiór dominujący".
- Dominating_set label "支配集合問題".
- Dominating_set sameAs Dominance_(graf).
- Dominating_set sameAs Conjunto_dominante.
- Dominating_set sameAs Ensemble_dominant.
- Dominating_set sameAs 支配集合問題.
- Dominating_set sameAs Dominerende_verzameling.
- Dominating_set sameAs Zbiór_dominujący.
- Dominating_set sameAs m.05sv8d.
- Dominating_set sameAs Q2915204.
- Dominating_set sameAs Q2915204.
- Dominating_set sameAs Dominating_set.
- Dominating_set wasDerivedFrom Dominating_set?oldid=569569420.
- Dominating_set depiction Dominating-set.svg.
- Dominating_set isPrimaryTopicOf Dominating_set.
