平面图选择控制集问题的复杂性分析及算法设计
研究平面图的选择控制集问题.通过PX3C(planar exact cover by 3-sets)到平面图控制集的变换,证明了平面图的控制集问题是NP完全的,从而得到平面图的选择控制集问题的NP完全性.同时提出了一个基于遗传算法的求平面赋权图的选择控制集的近似算法.
作 者： 陈方淦 孙良 作者单位： 北京理工大学,理学院数学系,北京,100081 刊 名： 北京理工大学学报 ISTIC EI PKU 英文刊名： TRANSACTIONS OF BEIJING INSTITUTE OF TECHNOLOGY 年，卷(期)： 2003 23(3) 分类号： O157.5 关键词： 选择控制集 平面图 复杂性 遗传算法