About: Dominating set

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

A set of vertices in a node-link graph such that every vertex is either in the set or adjacent to it

Property	Value
dbo:description	a gráf csúcsainak olyan részhalmaza, melyek zárt szomszédsága a gráf összes csúcsát tartalmazza (hu) typ podzbioru wierzchołków w grafie (pl) aro de verticoj en grafo tia, ke ĉiu vertico aŭ apartenas al la aro aŭ estasa apud vertico en la aro (eo) a set of vertices in a node-link graph such that every vertex is either in the set or adjacent to it (en)
dbo:thumbnail	wiki-commons:Special:FilePath/Dominating-set.svg?width=300
dbo:wikiPageExternalLink	http://www.mrfellows.net/papers/DFFPR06_Nonblocker.pdf https://archive.org/details/fundamentalsofdo0000hayn http://www.nada.kth.se/~viggo/wwwcompendium/node11.html http://drum.lib.umd.edu/bitstream/1903/830/4/CS-TR-3660.pdf https://www.csc.kth.se/~viggo/papers/phdthesis.pdf
dbo:wikiPageWikiLink	dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory dbr:Clique_(graph_theory) dbc:Graph_theory_objects dbr:Universe_(mathematics) dbr:Karp's_21_NP-complete_problems dbr:Lecture_Notes_in_Computer_Science dbr:Independent_set_(graph_theory) dbr:Matching_(graph_theory) dbr:Electrical_grid dbr:Forbidden_graph_characterization dbr:Claw-free_graph dbr:Split_graph dbr:Cartesian_product_of_graphs dbr:Set_cover_problem dbr:Isolated_vertex dbr:Graph_theory dbr:Subset dbr:Algorithmica dbr:Edge_dominating_set dbr:Induced_subgraph dbr:Computational_complexity_theory dbr:Complete_bipartite_graph dbr:Unit_disk_graph dbr:Maximal_independent_set dbr:Approximation_algorithm dbr:Polynomial-time_approximation_scheme dbr:Journal_of_the_ACM dbr:Branch-decomposition dbr:Discrete_Mathematics_(journal) dbr:Line_graph dbr:Dynamic_programming dbr:Graph_(discrete_mathematics) dbr:Planar_graph dbr:Spanning_tree dbr:ACM_SIGACT dbr:APX dbr:Symposium_on_Theory_of_Computing dbr:Decision_problem dbr:Star_(graph_theory) dbr:Connected_dominating_set dbr:Biclique-free_graph dbr:Eternal_dominating_set dbr:Nonblocker dbr:Wireless_networking dbr:L-reduction dbr:Series–parallel_graph dbr:Vizing's_conjecture dbr:Bondage_number dbr:NP-complete dbr:NP-hard dbr:Richard_Karp dbr:Royal_Institute_of_Technology dbr:P_=_NP dbr:Fixed-parameter_tractable dbr:Connected_(graph_theory) dbr:Document_summarization dbr:Domatic_partition dbr:W(2) dbr:Minimum_maximal_matching dbr:Polynomial-time_algorithm dbr:File:Dominating-set-2.svg dbr:File:Dominating-set-reduction.svg dbr:File:Dominating-set.svg
dbp:wikiPageUsesTemplate	dbt:Authority_control dbt:Reflist dbt:Math dbt:Sub dbt:For dbt:Radic dbt:Sup dbt:Citation dbt:Garey-Johnson dbt:Sfnp dbt:Mvar dbt:Abs dbt:Harvtxt dbt:Tmath dbt:Short_description
dct:subject	dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory dbc:Graph_theory_objects
gold:hypernym	dbr:D
rdfs:label	Dominating set (en) Dominance (graf) (cs) Dominierende Menge (de) Conjunto dominante (es) Ensemble dominant (fr) 支配集合問題 (ja) Dominerende verzameling (nl) Доминирующее множество (ru) Zbiór dominujący (pl) Conjunto dominante (pt) Домінівна множина (uk)
owl:sameAs	yago-res:Dominating set freebase:Dominating set wikidata:Dominating set dbpedia-nl:Dominating set dbpedia-de:Dominating set dbpedia-fr:Dominating set dbpedia-ja:Dominating set dbpedia-pt:Dominating set dbpedia-he:Dominating set dbpedia-es:Dominating set dbpedia-fa:Dominating set dbpedia-ru:Dominating set dbpedia-pl:Dominating set dbpedia-cs:Dominating set dbpedia-sr:Dominating set dbpedia-uk:Dominating set dbpedia-global:Dominating set
prov:wasDerivedFrom	wikipedia-en:Dominating_set?oldid=1288029678&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Dominating-set-2.svg wiki-commons:Special:FilePath/Dominating-set-reduction.svg wiki-commons:Special:FilePath/Dominating-set.svg
foaf:isPrimaryTopicOf	wikipedia-en:Dominating_set
is dbo:wikiPageRedirects of	dbr:Domination_number dbr:Independent_domination_number dbr:Dominating_set_problem dbr:Domination_perfect_graph dbr:Minimum_dominating_set dbr:Total_dominating_set
is dbo:wikiPageWikiLink of	dbr:Parameterized_complexity dbr:Planar_separator_theorem dbr:Hortensia_Galeana_Sánchez dbr:Teresa_W._Haynes dbr:Glossary_of_graph_theory dbr:Rooted_product_of_graphs dbr:András_Hajnal dbr:Independent_set_(graph_theory) dbr:Claw-free_graph dbr:Combinatorial_optimization dbr:Exponential_time_hypothesis dbr:Bidimensionality dbr:Set_cover_problem dbr:Graph_theory dbr:Bipartite_graph dbr:Edge_dominating_set dbr:Cubic_graph dbr:Domination_number dbr:Independent_domination_number dbr:Unit_disk_graph dbr:Domatic_number dbr:Pursuit–evasion dbr:Torsten_Suel dbr:Maximal_independent_set dbr:Domination_analysis dbr:Metric_k-center dbr:Vertex_k-center_problem dbr:Visibility_graph dbr:APX dbr:Gary_Chartrand dbr:Connected_dominating_set dbr:Biclique-free_graph dbr:Bounded_expansion dbr:Dually_chordal_graph dbr:Incidence_coloring dbr:Eternal_dominating_set dbr:Nonblocker dbr:L-reduction dbr:Split_(graph_theory) dbr:Michael_Scott_Jacobson dbr:Word-representable_graph dbr:Rainbow-independent_set dbr:Phyllis_Chinn dbr:Nondeterministic_constraint_logic dbr:Vizing's_conjecture dbr:Kieka_Mynhardt dbr:Odile_Favaron dbr:Independence_complex dbr:Weak_coloring dbr:Bishop's_graph dbr:Queen's_graph dbr:Universal_vertex dbr:Twin-width dbr:Dominating_set_problem dbr:Domination_perfect_graph dbr:Minimum_dominating_set dbr:Total_dominating_set
is owl:differentFrom of	dbr:Dominator_(graph_theory)
is foaf:primaryTopic of	wikipedia-en:Dominating_set