Dominating set: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) Нет описания правки |
AlexM (обсуждение | вклад) Нет описания правки |
||
| Строка 31: | Строка 31: | ||
The dominating set problem is ''NP''-complete on arbitrary graphs. It is | The dominating set problem is ''NP''-complete on arbitrary graphs. It is | ||
also ''NP'-complete on several classes of graphs, including planar | also ''NP''-complete on several classes of graphs, including planar | ||
graphs, bipartite graphs and ''chordal'' graphs. The problem can be solved | graphs, bipartite graphs and ''chordal'' graphs. The problem can be solved | ||
in polynomial time on, for example, AT-free graphs, ''permutation graphs, interval graphs'', and trees. | in polynomial time on, for example, AT-free graphs, ''permutation graphs, interval graphs'', and trees. | ||
==See also== | ==See also== | ||
*''<math>k</math>-restricted total dominating number''. | *''<math>k</math>-restricted total dominating number''. | ||