论文标题
在完美消除双方图中的红色统治
Red Domination in Perfect Elimination Bipartite Graphs
论文作者
论文摘要
$ k $红色的统治问题的两部分图$ g =（x，y，e）$是找到一个$ k $的子集$ d \ subseteq x $的基数，该$ k $主导了$ y $的顶点。该问题的决策版本对于一般的两部分图是NP完整的，但在多项式时间内可用于弦弦两分数。我们通过证明它是完美的消除双方图是NP完整的，从而加强了这一结果。我们在两部分图中的此类集合数上呈现一个紧密的上限，并表明我们可以在线性时间中计算出凸两部分图的线性时间。我们提出了仅需要线性预处理时间的线性空间线性延迟枚举算法。
The $k$ red domination problem for a bipartite graph $G=(X,Y,E)$ is to find a subset $D \subseteq X$ of cardinality at most $k$ that dominates vertices of $Y$. The decision version of this problem is NP-complete for general bipartite graphs but solvable in polynomial time for chordal bipartite graphs. We strengthen that result by showing that it is NP-complete for perfect elimination bipartite graphs. We present a tight upper bound on the number of such sets in bipartite graphs, and show that we can calculate that number in linear time for convex bipartite graphs. We present a linear space linear delay enumeration algorithm that needs only linear preprocessing time.
