哈林图中划分成完美对集问题的线性算法

摘要：

图G=(V,E),正整数K≤|V|,G的顶点是否能划分成k≤K个不相交的集合V1, V2,…,Vk, 使得对于i∈{1,…,k},由Vi诱导的子图是一个完美对集.这个问题是一个NP完全问题.给出在哈林图上求最小K值的算法.算法的时间复杂度是O(n).

关键词：哈林图、完美对集、划分

所属期刊栏目：9

分类号：TP301.6(计算技术、计算机技术)

资助基金：深圳信息职业技术学院院内理工基金QN-08003

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

页数：共7页

页码：4366-4371,4376