论文标题
在Co-Biconvex图和Web图上进行元组支配的有效算法
Efficient algorithms for tuple domination on co-biconvex graphs and web graphs
论文作者
论文摘要
图中的顶点及其每个相邻顶点占主导地位。对于固定的正整数$ k $，\ emph {$ k $ -tuple统治问题}是在给定图中找到一个最小尺寸的顶点子集，以使每个顶点至少由该集合的至少$ k $ pertices主导。从计算的角度来看，这个问题是NP-HARD。 It follows from previous works by Bui-Xuan et al.~(2013) and by Belmonte et al.~(2013) -- in the context of locally checkable vertex subset problems in graph classes with quickly computable and bounded min-width -- that the $k$-tuple domination problem is solvable in time $\mathcal{O}(|V(G)|^{6k+4})$ in the class of圆形弧形图。在这项工作中，我们为Co-Biconvex图和Web图中的$ k $ tuple支配而开发了更快的算法，这些算法是无与伦比的凹入图的亚类，因此是圆形ARC图的子类。一方面，我们提出了一个$ \ MATHCAL {O}（n^2）$ - 用于解决每个$ 2 \ leq k \ leq | U |+3 $求解的时间算法，其中$ u $是$ u $的集合，是$ n $ $ n $输入Co-Biconvex图的总数。另一方面，Argiroffo等人已经启动了网络图上此问题的研究。 （2010）从多面体的角度出发，仅对于$ k = 2 $和$ k = d（g）$，其中$ d（g）$等于输入Web Graph $ g $的每个顶点的度量。我们通过基于整数数字的模块化算术设计线性时间算法来从算法的角度完成这项研究的Web图。这项工作中提出的算法是相互独立的，但两者都利用了每个研究的图类别的增强邻接矩阵的圆形特性。
A vertex in a graph dominates itself and each of its adjacent vertices. The \emph{$k$-tuple domination problem}, for a fixed positive integer $k$, is to find a minimum sized vertex subset in a given graph such that every vertex is dominated by at least $k$ vertices of this set. From the computational point of view, this problem is NP-hard. It follows from previous works by Bui-Xuan et al.~(2013) and by Belmonte et al.~(2013) -- in the context of locally checkable vertex subset problems in graph classes with quickly computable and bounded min-width -- that the $k$-tuple domination problem is solvable in time $\mathcal{O}(|V(G)|^{6k+4})$ in the class of circular-arc graphs. In this work, we develop faster algorithms for $k$-tuple domination in co-biconvex graphs and in web graphs, which are incomparable subclasses of concave-round graphs and thus of circular-arc graphs. On the one hand, we present an $\mathcal{O}(n^2)$-time algorithm for solving it for each $2\leq k\leq |U|+3$, where $U$ is the set of universal vertices and $n$ the total number of vertices of the input co-biconvex graph. On the other hand, the study of this problem on web graphs was already started by Argiroffo et al. (2010) from a polyhedral point of view only for the cases $k=2$ and $k=d(G)$, where $d(G)$ equals the degree of each vertex of the input web graph $G$. We complete this study for web graphs from an algorithmic point of view, by designing a linear-time algorithm based on the modular arithmetic for integer numbers. The algorithms presented in this work are mutually independent but both exploit the circular properties of the augmented adjacency matrices of each studied graph class.
