| dbo:abstract |
Dominancí grafu označujeme mohutnost minimální dominující množiny uzlů. Dominující množinou je taková množina uzlů, která svou množinou sousedních uzlů pokrývá všechny zbývají uzly grafu. (cs) 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. (en) El conjunto dominante de un grafo G = (V, E) es un subconjunto V' de V tal que cada vértice que no pertenezca a V' está unido a (al menos) un miembro de V'. El número dominante γ(G) es el cardinal del menor conjunto dominante de G. El problema de la dominación en grafos ha sido estudiado desde la década de los cincuenta, pero el interés por esta área creció significativamente a mediados de los setenta (Hedetniemi y Laskar, 1990). (es) En théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donnés G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet. (fr) 支配集合問題（しはいしゅうごうもんだい、英: dominating set）は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ G(V, E) の頂点集合 V′ (⊆ V) で、V′ に属さない全ての頂点 v について、v の隣接頂点のいずれか一つが V′ に属するような V′ （支配集合）のうち、最小のものを求める問題。 この問題は、集合被覆問題に含まれるため、集合被覆問題への近似アルゴリズムを適用することで近似度 1 + log|V |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Dominating-set.svg?width=300 |
| dbo:wikiPageExternalLink |
http://www.mrfellows.net/papers/DFFPR06_Nonblocker.pdf http://drum.lib.umd.edu/bitstream/1903/830/4/CS-TR-3660.pdf https://www.csc.kth.se/~viggo/papers/phdthesis.pdf https://archive.org/details/fundamentalsofdo0000hayn http://www.nada.kth.se/~viggo/wwwcompendium/node11.html |
| dbo:wikiPageID |
1747972 (xsd:integer) |
| dbo:wikiPageLength |
31725 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1122928837 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Electrical_grid dbr:Algorithmica dbr:Approximation_algorithm dbr:Universe_(mathematics) dbr:Vizing's_conjecture dbr:Decision_problem dbr:Independent_set_(graph_theory) dbr:Induced_subgraph dbr:L-reduction dbr:Isolated_vertex dbc:Graph_theory_objects dbc:NP-complete_problems dbr:Complete_bipartite_graph dbr:Matching_(graph_theory) dbr:Maximal_independent_set dbr:Graph_(discrete_mathematics) dbr:Branch-decomposition dbr:NP-complete dbr:NP-hard dbr:Connected_dominating_set dbr:Line_graph dbr:Star_(graph_theory) dbr:Claw-free_graph dbr:Clique_(graph_theory) dbr:Computational_complexity_theory dbr:Spanning_tree dbr:Karp's_21_NP-complete_problems dbr:Lecture_Notes_in_Computer_Science dbr:Dynamic_programming dbr:Forbidden_graph_characterization dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Journal_of_the_ACM dbr:Fixed-parameter_tractable dbr:ACM_SIGACT dbr:APX dbr:Biclique-free_graph dbc:Computational_problems_in_graph_theory dbr:Edge_dominating_set dbr:Bondage_number dbr:Planar_graph dbr:Polynomial-time_approximation_scheme dbr:Split_graph dbr:Document_summarization dbr:Domatic_partition dbr:Cartesian_product_of_graphs dbr:Royal_Institute_of_Technology dbr:Set_cover_problem dbr:Symposium_on_Theory_of_Computing dbr:Unit_disk_graph dbr:Eternal_dominating_set dbr:Series–parallel_graph dbr:Nonblocker dbr:Subset dbr:W(2) dbr:Minimum_maximal_matching dbr:Richard_Karp dbr:P_=_NP dbr:Wireless_networking dbr:Polynomial-time_algorithm dbr:Connected_(graph_theory) dbr:File:Dominating-set-2.svg dbr:File:Dominating-set-reduction.svg dbr:File:Dominating-set.svg |
| dbp:wikiPageUsesTemplate |
dbt:Authority_control dbt:Citation dbt:For dbt:Harvtxt dbt:Math dbt:Mvar dbt:Radic dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Sub dbt:Sup dbt:Tmath dbt:Abs dbt:Garey-Johnson |
| dct:subject |
dbc:Graph_theory_objects dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory |
| gold:hypernym |
dbr:D |
| rdf:type |
owl:Thing yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Cognition100023271 yago:Concept105835747 yago:Condition113920835 yago:Content105809192 yago:Difficulty114408086 yago:Family108078020 yago:Feature105849789 yago:Group100031264 yago:Idea105833840 yago:Invariant105850432 yago:Organization108008335 yago:Problem114410605 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphFamilies yago:WikicatGraphInvariants yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity dbo:VideoGame yago:SocialGroup107950920 yago:State100024720 yago:Unit108189659 |
| rdfs:comment |
Dominancí grafu označujeme mohutnost minimální dominující množiny uzlů. Dominující množinou je taková množina uzlů, která svou množinou sousedních uzlů pokrývá všechny zbývají uzly grafu. (cs) El conjunto dominante de un grafo G = (V, E) es un subconjunto V' de V tal que cada vértice que no pertenezca a V' está unido a (al menos) un miembro de V'. El número dominante γ(G) es el cardinal del menor conjunto dominante de G. El problema de la dominación en grafos ha sido estudiado desde la década de los cincuenta, pero el interés por esta área creció significativamente a mediados de los setenta (Hedetniemi y Laskar, 1990). (es) En théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donnés G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet. (fr) 支配集合問題（しはいしゅうごうもんだい、英: dominating set）は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ G(V, E) の頂点集合 V′ (⊆ V) で、V′ に属さない全ての頂点 v について、v の隣接頂点のいずれか一つが V′ に属するような V′ （支配集合）のうち、最小のものを求める問題。 この問題は、集合被覆問題に含まれるため、集合被覆問題への近似アルゴリズムを適用することで近似度 1 + log|V |
| rdfs:label |
Dominance (graf) (cs) Dominierende Menge (de) Conjunto dominante (es) Dominating set (en) Ensemble dominant (fr) 支配集合問題 (ja) Dominerende verzameling (nl) Zbiór dominujący (pl) Доминирующее множество (ru) Conjunto dominante (pt) Домінівна множина (uk) |
| owl:sameAs |
freebase:Dominating set yago-res:Dominating set wikidata:Dominating set dbpedia-cs:Dominating set dbpedia-de:Dominating set dbpedia-es:Dominating set dbpedia-fa:Dominating set dbpedia-fr:Dominating set dbpedia-he:Dominating set dbpedia-ja:Dominating set dbpedia-nl:Dominating set dbpedia-pl:Dominating set dbpedia-pt:Dominating set dbpedia-ru:Dominating set dbpedia-sr:Dominating set dbpedia-uk:Dominating set https://global.dbpedia.org/id/2hnKc |
| prov:wasDerivedFrom |
wikipedia-en:Dominating_set?oldid=1122928837&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:Total_dominating_set dbr:Domination_number dbr:Independent_domination_number dbr:Domination_perfect_graph dbr:Dominating_set_problem dbr:Minimum_dominating_set |
| is dbo:wikiPageWikiLink of |
dbr:Queen's_graph dbr:Metric_k-center dbr:Total_dominating_set dbr:András_Hajnal dbr:Cubic_graph dbr:Vizing's_conjecture dbr:Domination_analysis dbr:Domination_number dbr:Incidence_coloring dbr:Independence_complex dbr:Independent_domination_number dbr:Independent_set_(graph_theory) dbr:L-reduction dbr:Maximal_independent_set dbr:Pursuit–evasion dbr:Gary_Chartrand dbr:Glossary_of_graph_theory dbr:Bounded_expansion dbr:Connected_dominating_set dbr:Claw-free_graph dbr:Combinatorial_optimization dbr:Hortensia_Galeana_Sánchez dbr:Planar_separator_theorem dbr:Split_(graph_theory) dbr:Michael_Scott_Jacobson dbr:Weak_coloring dbr:Domatic_number dbr:Dually_chordal_graph dbr:Graph_theory dbr:Kieka_Mynhardt dbr:APX dbr:Biclique-free_graph dbr:Bidimensionality dbr:Bipartite_graph dbr:Bishop's_graph dbr:Edge_dominating_set dbr:Domination_perfect_graph dbr:Phyllis_Chinn dbr:Dominating_set_problem dbr:Rainbow-independent_set dbr:Set_cover_problem dbr:Unit_disk_graph dbr:Eternal_dominating_set dbr:Exponential_time_hypothesis dbr:Odile_Favaron dbr:Visibility_graph dbr:Universal_vertex dbr:Vertex_k-center_problem dbr:Rooted_product_of_graphs dbr:Nonblocker dbr:Nondeterministic_constraint_logic dbr:Torsten_Suel dbr:Parameterized_complexity dbr:Twin-width dbr:Teresa_W._Haynes dbr:Word-representable_graph dbr:Minimum_dominating_set |
| is owl:differentFrom of |
dbr:Dominator_(graph_theory) |
| is foaf:primaryTopic of |
wikipedia-en:Dominating_set |
