Upper Domination: Towards a Dichotomy Through Boundary Properties
Upper Domination: Towards a Dichotomy Through Boundary Properties
复制标题
上层统治：通过边界属性走向二分法
DOI：
10.1007/s00453-017-0346-9
复制
发表时间：
2017
期刊：
影响因子：
1.1
通讯作者：
AbouEisha H
中科院分区：
文献类型：
--
作者：
AbouEisha H
图的上控制集是最大基数的极小控制集。寻找上支配集的问题一般是NP难的。我们在有限定义的图类中研究了该问题的复杂性，并猜想该问题在这一族中具有复杂性二分法。研究算法问题复杂性的一个有用工具是边界类的概念。然而，到目前为止，还没有一个这样的类被确定为上控制集问题。我们发现了这个问题的第一个边界类，并证明了单因类的二分性。
An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.
登录
查看更多内容
DOI：
10.1016/j.ipl.2013.01.022
发表时间：
2013
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
V. Lozin;Christopher Purcell
通讯作者：
Christopher Purcell
DOI：
10.1007/10692760_1
发表时间：
1998-06
期刊：
--
影响因子：
--
作者：
B. Courcelle;J. Makowsky;Udi Rotics
通讯作者：
B. Courcelle;J. Makowsky;Udi Rotics
DOI：
10.1016/0012-365x(81)90268-5
发表时间：
1981
期刊：
Discret. Math.
影响因子：
--
作者：
E. Cockayne;O. Favaron;C. Payan;A. Thomason
通讯作者：
E. Cockayne;O. Favaron;C. Payan;A. Thomason
影响因子：
1.1
作者：
N. Korpelainen;V. Lozin;D. Malyshev;A. Tiskin
通讯作者：
A. Tiskin
影响因子：
0.9
作者：
V. Lozin;V. Zamaraev
通讯作者：
V. Zamaraev