Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Dominating_set> ?p ?o }
- 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 phdthesis.pdf.
- Dominating_set wikiPageExternalLink node11.html.
- Dominating_set wikiPageExternalLink algorithms.dominating.html.
- Dominating_set wikiPageID "1747972".
- Dominating_set wikiPageLength "24540".
- Dominating_set wikiPageOutDegree "68".
- Dominating_set wikiPageRevisionID "704213350".
- Dominating_set wikiPageWikiLink ACM_SIGACT.
- Dominating_set wikiPageWikiLink APX.
- Dominating_set wikiPageWikiLink Algorithmica.
- Dominating_set wikiPageWikiLink Approximation_algorithm.
- Dominating_set wikiPageWikiLink BSD_licenses.
- Dominating_set wikiPageWikiLink Biclique-free_graph.
- Dominating_set wikiPageWikiLink Bondage_number.
- Dominating_set wikiPageWikiLink Branch-decomposition.
- Dominating_set wikiPageWikiLink Cartesian_product_of_graphs.
- Dominating_set wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Dominating_set wikiPageWikiLink Category:Graph_theory_objects.
- Dominating_set wikiPageWikiLink Category:NP-complete_problems.
- Dominating_set wikiPageWikiLink Claw-free_graph.
- Dominating_set wikiPageWikiLink Clique_(graph_theory).
- Dominating_set wikiPageWikiLink Complete_bipartite_graph.
- Dominating_set wikiPageWikiLink Computational_complexity_theory.
- Dominating_set wikiPageWikiLink Connected_dominating_set.
- Dominating_set wikiPageWikiLink Decision_problem.
- Dominating_set wikiPageWikiLink Discrete_Mathematics_(journal).
- Dominating_set wikiPageWikiLink Domatic_number.
- Dominating_set wikiPageWikiLink Dynamic_programming.
- Dominating_set wikiPageWikiLink Edge_dominating_set.
- Dominating_set wikiPageWikiLink Eternal_dominating_set.
- Dominating_set wikiPageWikiLink Forbidden_graph_characterization.
- Dominating_set wikiPageWikiLink Graph_(discrete_mathematics).
- Dominating_set wikiPageWikiLink Graph_theory.
- Dominating_set wikiPageWikiLink Independent_set_(graph_theory).
- Dominating_set wikiPageWikiLink Induced_subgraph.
- Dominating_set wikiPageWikiLink Journal_of_the_ACM.
- Dominating_set wikiPageWikiLink Karps_21_NP-complete_problems.
- Dominating_set wikiPageWikiLink L-reduction.
- Dominating_set wikiPageWikiLink Lecture_Notes_in_Computer_Science.
- Dominating_set wikiPageWikiLink Line_graph.
- Dominating_set wikiPageWikiLink Matching_(graph_theory).
- Dominating_set wikiPageWikiLink Maximal_independent_set.
- Dominating_set wikiPageWikiLink NP-completeness.
- Dominating_set wikiPageWikiLink NP-hardness.
- Dominating_set wikiPageWikiLink NetworkX.
- Dominating_set wikiPageWikiLink OpenOpt.
- Dominating_set wikiPageWikiLink P_versus_NP_problem.
- Dominating_set wikiPageWikiLink Parameterized_complexity.
- Dominating_set wikiPageWikiLink Planar_graph.
- Dominating_set wikiPageWikiLink Polynomial-time_approximation_scheme.
- Dominating_set wikiPageWikiLink Royal_Institute_of_Technology.
- Dominating_set wikiPageWikiLink Series-parallel_graph.
- Dominating_set wikiPageWikiLink Set_cover_problem.
- Dominating_set wikiPageWikiLink Spanning_tree.
- Dominating_set wikiPageWikiLink Split_graph.
- Dominating_set wikiPageWikiLink Subset.
- Dominating_set wikiPageWikiLink Symposium_on_Theory_of_Computing.
- Dominating_set wikiPageWikiLink Time_complexity.
- Dominating_set wikiPageWikiLink Unit_disk_graph.
- Dominating_set wikiPageWikiLink Vizings_conjecture.
- Dominating_set wikiPageWikiLink File:Dominating-set-2.svg.
- Dominating_set wikiPageWikiLink File:Dominating-set-reduction.svg.
- Dominating_set wikiPageWikiLink File:Dominating-set.svg.
- Dominating_set wikiPageWikiLinkText "Dominating set".
- Dominating_set wikiPageWikiLinkText "Dominating set#Independent domination".
- Dominating_set wikiPageWikiLinkText "Dominating_set".
- Dominating_set wikiPageWikiLinkText "Min Dominating Set".
- Dominating_set wikiPageWikiLinkText "dominating set".
- Dominating_set wikiPageWikiLinkText "domination in graphs".
- Dominating_set wikiPageWikiLinkText "domination number".
- Dominating_set wikiPageWikiLinkText "domination".
- Dominating_set wikiPageUsesTemplate Template:Citation.
- Dominating_set wikiPageUsesTemplate Template:For.
- Dominating_set wikiPageUsesTemplate Template:Garey-Johnson.
- Dominating_set wikiPageUsesTemplate Template:Harv.
- Dominating_set wikiPageUsesTemplate Template:Harvtxt.
- Dominating_set wikiPageUsesTemplate Template:Reflist.
- 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 hypernym D.
- Dominating_set type VideoGame.
- Dominating_set type Graph.
- Dominating_set type Invariant.
- Dominating_set type Object.
- Dominating_set type Redirect.
- 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 "Dominating set".
- Dominating_set sameAs Q2915204.
- Dominating_set sameAs Dominance_(graf).
- Dominating_set sameAs Conjunto_dominante.
- Dominating_set sameAs مجموعه_غالب.
- Dominating_set sameAs Ensemble_dominant.
- Dominating_set sameAs קבוצה_שולטת.
- Dominating_set sameAs 支配集合問題.
- Dominating_set sameAs Dominerende_verzameling.
- Dominating_set sameAs Zbiór_dominujący.
- Dominating_set sameAs Conjunto_dominante.