Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Eternal_dominating_set> ?p ?o }
Showing triples 1 to 34 of
34
with 100 triples per page.
- Eternal_dominating_set abstract "In graph theory, an eternal dominating set for a graph G = (V, E) is a subset D of V such that D is a dominating set on which mobile guards are initially located (at most one guard may be located on any vertex). The set D must be such that for any infinite sequence of attacks occurring sequentially at vertices, the set D can be modified by moving a guard from an adjacent vertex to the attacked vertex, provided the attacked vertex has no guard on it at the time it is attacked. The configuration of guards after each attack must induce a dominating set. The eternal domination number, γ∞(G), is the minimum number of vertices possible in the initial set D. For example, the eternal domination number of the cycle on five vertices is three.The eternal dominating set problem, also known as the eternal domination problem and the eternal security problem, can also be interpreted as a combinatorial game played between two players that alternate turns: a defender, who chooses the initial dominating set D and the guard to send to each attack that occurs at a vertex without a guard; and an attacker, who chooses the vertex to be attacked on their turn. The attacker wins the game if they can ever choose a vertex to be attacked such that there is no guard on that vertex or a neighboring vertex; the defender wins otherwise. In other words, the attacker wins the game if they can ever attack a vertex such that the attack cannot be defended.As noted in Klostermeyer & Mynhardt (2015b), the eternal dominating set problem is related to the k-server problem in computer science.".
- Eternal_dominating_set wikiPageExternalLink 1407.5228.
- Eternal_dominating_set wikiPageExternalLink MES.ps.
- Eternal_dominating_set wikiPageExternalLink eterndom.html.
- Eternal_dominating_set wikiPageID "45455813".
- Eternal_dominating_set wikiPageLength "13393".
- Eternal_dominating_set wikiPageOutDegree "13".
- Eternal_dominating_set wikiPageRevisionID "705120990".
- Eternal_dominating_set wikiPageWikiLink Category:Graph_theory_objects.
- Eternal_dominating_set wikiPageWikiLink Cayley_graph.
- Eternal_dominating_set wikiPageWikiLink Combinatorial_game_theory.
- Eternal_dominating_set wikiPageWikiLink Dominating_set.
- Eternal_dominating_set wikiPageWikiLink Douglas_West_(mathematician).
- Eternal_dominating_set wikiPageWikiLink Graph_(discrete_mathematics).
- Eternal_dominating_set wikiPageWikiLink Graph_coloring.
- Eternal_dominating_set wikiPageWikiLink Graph_theory.
- Eternal_dominating_set wikiPageWikiLink K-server_problem.
- Eternal_dominating_set wikiPageWikiLink Lovász_number.
- Eternal_dominating_set wikiPageWikiLink Perfect_graph_theorem.
- Eternal_dominating_set wikiPageWikiLink Subset.
- Eternal_dominating_set wikiPageWikiLink Vizings_conjecture.
- Eternal_dominating_set wikiPageWikiLinkText "Eternal dominating set".
- Eternal_dominating_set wikiPageUsesTemplate Template:Citation.
- Eternal_dominating_set wikiPageUsesTemplate Template:Harv.
- Eternal_dominating_set wikiPageUsesTemplate Template:Harvtxt.
- Eternal_dominating_set wikiPageUsesTemplate Template:Reflist.
- Eternal_dominating_set subject Category:Graph_theory_objects.
- Eternal_dominating_set hypernym D.
- Eternal_dominating_set type VideoGame.
- Eternal_dominating_set comment "In graph theory, an eternal dominating set for a graph G = (V, E) is a subset D of V such that D is a dominating set on which mobile guards are initially located (at most one guard may be located on any vertex). The set D must be such that for any infinite sequence of attacks occurring sequentially at vertices, the set D can be modified by moving a guard from an adjacent vertex to the attacked vertex, provided the attacked vertex has no guard on it at the time it is attacked.".
- Eternal_dominating_set label "Eternal dominating set".
- Eternal_dominating_set sameAs m.012zlhjf.
- Eternal_dominating_set wasDerivedFrom Eternal_dominating_set?oldid=705120990.
- Eternal_dominating_set isPrimaryTopicOf Eternal_dominating_set.