论文标题
寻找$ s_ {1,3,3} $的高效支配 - 在多项式时间中
Finding Efficient Domination for $S_{1,3,3}$-Free Bipartite Graphs in Polynomial Time
论文作者
论文摘要
有限的无向图$ g $中的顶点集$ d $是{\ em效率的主导集}（\ emph {emph {e.d.s。} \ for Short）的$ g $，如果$ g $的每个顶点恰好由$ d $的一个顶点支配到$ g $。 \ emph {有效的统治}（ed）问题，要求在$ g $中存在e.d.s. \，对于各种$ h $ h $ free双分部分图是\ np complete，例如lu和tang显示，lu and tang表明ed ed ed ed \ np是Chordal Biptite图形和Planar Bipartite for Planar Bipartite for Planar bipartite for Planar bipartite for Planar bipartite for Planar bipartite for planar bipartite for Planar bipartite；实际上，即使对于具有顶点学位的平面两分图，ED也是\ np的完整，最多也是3个，每个固定的$ g $至少围绕着$ g $。因此，ED是$ k_ {1,4} $的\ np-Complete-免费的双分图和$ C_4 $ - FREE-FREE双方图。 在本文中，我们表明可以在多项式时间内以$ s_ {1,3,3} $ - 免费的双分图形来解决ED。
A vertex set $D$ in a finite undirected graph $G$ is an {\em efficient dominating set} (\emph{e.d.s.}\ for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$. The \emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d.s.\ in $G$, is \NP-complete for various $H$-free bipartite graphs, e.g., Lu and Tang showed that ED is \NP-complete for chordal bipartite graphs and for planar bipartite graphs; actually, ED is \NP-complete even for planar bipartite graphs with vertex degree at most 3 and girth at least $g$ for every fixed $g$. Thus, ED is \NP-complete for $K_{1,4}$-free bipartite graphs and for $C_4$-free bipartite graphs. In this paper, we show that ED can be solved in polynomial time for $S_{1,3,3}$-free bipartite graphs.
