Nonblocker
http://dbpedia.org/resource/Nonblocker
In graph theory, a nonblocker is a subset of vertices in an undirected graph, all of which are adjacent to vertices outside of the subset. Equivalently, a nonblocker is the complement of a dominating set. The computational problem of finding the largest nonblocker in a graph was formulated by , who observed that it belongs to MaxSNP.Although computing a dominating set is not fixed-parameter tractable under standard assumptions, the complementary problem of finding a nonblocker of a given size is fixed-parameter tractable.
rdf:langString
rdf:langString
Nonblocker
xsd:integer
56012715
xsd:integer
1106185044
rdf:langString
In graph theory, a nonblocker is a subset of vertices in an undirected graph, all of which are adjacent to vertices outside of the subset. Equivalently, a nonblocker is the complement of a dominating set. The computational problem of finding the largest nonblocker in a graph was formulated by , who observed that it belongs to MaxSNP.Although computing a dominating set is not fixed-parameter tractable under standard assumptions, the complementary problem of finding a nonblocker of a given size is fixed-parameter tractable. In graphs with no isolated vertices, every maximal nonblocker (one to which no more vertices can be added) is itself a dominating set.
xsd:nonNegativeInteger
4975
