Domination on Cocomparability Graphs

Domination on Cocomparability Graphs
复制标题

DOI：
10.1137/0406032
复制
发表时间：
1993-08
期刊：
SIAM J. Discret. Math.
影响因子：
--
通讯作者：
D. Kratsch;Lorna Stewart
D. Kratsch;Lorna Stewart
中科院分区：
其他
文献类型：
--
作者：
D. Kratsch;Lorna Stewart

文献摘要

被引文献

相似文献

作者确定了算法的复杂性的控制和变异的协可比图，一类完美的图，包含的区间和置换图。最小控制集、全控制集、连通控制集和独立控制集可以在多项式时间内构造。另一方面，支配CLIQUE和MINIMUM DOMINATING CLIQUE在协可比图上仍然是NP完全的。
The authors determine the algorithmic complexity of domination and variants on cocomparability graphs, a class of perfect graphs containing both the interval and the permutation graphs. Minimum dominating, total dominating, connected dominating, and independent dominating sets can be constructed in polynomial time. On the other hand, DOMINATING CLIQUE and MINIMUM DOMINATING CLIQUE remain NP-complete on cocomparability graphs.