论文标题
防御性统治在适当的间隔图中
Defensive Domination in Proper Interval Graphs
论文作者
论文摘要
$ k $防御性的统治是图表上经典统治问题的一种变体，它寻求最小的基数顶点集，从而为对受参数$ k $界定的基数攻击的任何攻击提供了过滤性防御。对于固定的$ k $，该问题已被证明为np-Complete}；如果$ k $是输入的一部分，则问题甚至不在NP中。我们提出有效的算法，在使用$ k $的一部分输入的适当间隔图上解决此问题。该算法利用了与顶点相关的间隔的终点的线性顺序，以实现贪婪的解决方案方法。第一个算法基于间隔模型，具有复杂性$ {\ cal o}（n \ cdot k）$用于$ n $ vertices上的图形。第二个是对第一个的改进，并采用适当的间隔图的气泡表示，以实现$ {\ cal o}的改善复杂性（n+ \ vert {\ cal b} \ vert \ vert \ cdot \ log k）$，用于$ \ vert {\ cal b} \ vert $ bubble。
$k$-defensive domination, a variant of the classical domination problem on graphs, seeks a minimum cardinality vertex set providing a surjective defense against any attack on vertices of cardinality bounded by a parameter $k$. The problem has been shown to be NP-complete} for fixed $k$; if $k$ is part of the input, the problem is not even in NP. We present efficient algorithms solving this problem on proper interval graphs with $k$ part of the input. The algorithms take advantage of the linear orderings of the end points of the intervals associated with vertices to realize a greedy approach to solution. The first algorithm is based on the interval model and has complexity ${\cal O}(n \cdot k)$ for a graph on $n$ vertices. The second one is an improvement of the first and employs bubble representations of proper interval graph to realize an improved complexity of ${\cal O}(n+ \vert{\cal B}\vert \cdot \log k)$ for a graph represented by $\vert{\cal B}\vert$ bubbles.
