| dbo:abstract |
In graph theory, an edge dominating set for a graph G = (V, E) is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An edge dominating set is also known as a line dominating set. Figures (a)–(d) are examples of edge dominating sets (thick red lines). A minimum edge dominating set is a smallest edge dominating set. Figures (a) and (b) are examples of minimum edge dominating sets (it can be checked that there is no edge dominating set of size 2 for this graph). (en) В теории графов доминирующее множество рёбер (или рёберное доминирующее множество) графа G = (V, E) — это подмножество D ⊆ E, такое, что любое ребро не из D смежно по меньшей мере одному ребру из D. На рисунках (a)–(d) приведены примеры доминирующих множеств рёбер (красные рёбра). Наименьшее доминирующее множество рёбер — это доминирующие множества рёбер с наименьшим размером. На рисунках (a) и (b) представлены примеры наименьших доминирующих множеств рёбер (можно проверить, что для данного графа не существует доминирующего множества из двух рёбер). (ru) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Edge-dominating-set.svg?width=300 |
| dbo:wikiPageExternalLink |
https://researchportal.port.ac.uk/portal/en/publications/approximation-hardness-of-edge-dominating-set-problems(2759347d-cc3e-48f6-a6a4-0b943e7fb377).html http://dl.acm.org/citation.cfm%3Fid=545381.545419 http://www.csc.kth.se/~viggo/wwwcompendium/ http://www.csc.kth.se/~viggo/wwwcompendium/node13.html http://www.csc.kth.se/~viggo/wwwcompendium/node21.html |
| dbo:wikiPageID |
21689422 (xsd:integer) |
| dbo:wikiPageLength |
5911 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1035648620 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Approximation_algorithm dbc:NP-complete_problems dbr:NP-complete dbr:NP-hard dbr:Line_graph dbr:Gerhard_J._Woeginger dbr:Graph_theory dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Dominating_set dbr:Planar_graph dbr:Maximal_matching dbr:Minimum_maximal_matching dbr:File:Edge-dominating-set.svg |
| dbp:wikiPageUsesTemplate |
dbt:Citation dbt:Harvtxt dbt:See dbt:Harvnb |
| dcterms:subject |
dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory |
| gold:hypernym |
dbr:E |
| rdf:type |
yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 dbo:Album yago:State100024720 |
| rdfs:comment |
In graph theory, an edge dominating set for a graph G = (V, E) is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An edge dominating set is also known as a line dominating set. Figures (a)–(d) are examples of edge dominating sets (thick red lines). A minimum edge dominating set is a smallest edge dominating set. Figures (a) and (b) are examples of minimum edge dominating sets (it can be checked that there is no edge dominating set of size 2 for this graph). (en) В теории графов доминирующее множество рёбер (или рёберное доминирующее множество) графа G = (V, E) — это подмножество D ⊆ E, такое, что любое ребро не из D смежно по меньшей мере одному ребру из D. На рисунках (a)–(d) приведены примеры доминирующих множеств рёбер (красные рёбра). Наименьшее доминирующее множество рёбер — это доминирующие множества рёбер с наименьшим размером. На рисунках (a) и (b) представлены примеры наименьших доминирующих множеств рёбер (можно проверить, что для данного графа не существует доминирующего множества из двух рёбер). (ru) |
| rdfs:label |
Edge dominating set (en) Доминирующее множество рёбер (ru) Домінівна множина ребер (uk) |
| owl:sameAs |
freebase:Edge dominating set yago-res:Edge dominating set wikidata:Edge dominating set dbpedia-ru:Edge dominating set dbpedia-uk:Edge dominating set https://global.dbpedia.org/id/4iUoH |
| prov:wasDerivedFrom |
wikipedia-en:Edge_dominating_set?oldid=1035648620&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Edge-dominating-set.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Edge_dominating_set |
| is dbo:wikiPageRedirects of |
dbr:Dominating_edge_set |
| is dbo:wikiPageWikiLink of |
dbr:Matching_(graph_theory) dbr:List_of_NP-complete_problems dbr:Baker's_technique dbr:Bidimensionality dbr:Dominating_set dbr:Dominating_edge_set |
| is foaf:primaryTopic of |
wikipedia-en:Edge_dominating_set |
