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

摘要：

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

关键词：选择控制集、平面图、复杂性、遗传算法

所属期刊栏目：23

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：274-276