平面图选择控制集问题的复杂性分析及算法设计

On the Complexity and Algorithm of Optional Dominating Set on Planar Graphs

摘要: 研究平面图的选择控制集问题.通过PX3C(planarexactcoverby3-sets)到平面图控制集的变换,证明了平面图的控制集问题是NP完全的,从而得到平面图的选择控制集问题的NP完全性.同时提出了一个基于遗传算法的求平面赋权图的选择控制集的近似算法.

Abstract: Optional dominating set on planar graphs is studied. By a transformation from PX3C to dominating set on planar graphs, the paper shows that the problem of decision of dominating set on planar graphs is NP complete. The NP completeness of optional dominating set on planar graphs is thus proved. A proximate algorithm based genetic algorithm on the problem is thereby proposed.