网络分解及最大独立集算法研究(II)  

Network Decomposition and a New Algorithm for Maximum Independent Set(II)

作　　者：朱松年[1] 朱嫱 

机构地区：[1]西南交通大学交通运输学院,成都610031 [2]Geac计算机公司

出　　处：《交通运输工程与信息学报》2004年第1期1-11,共11页Journal of Transportation Engineering and Information

摘　　要：本文首先分析了一般连通网络的结构特征,发现了网络中具有优化迭代功能的特殊子网络;并对其进行了较深入的研究,提出并论证了求最大独立集的充要条件。进一步的研究发现,此特殊子网络及其邻域,具有相依、相斥的偶对性质;若按某种方式将连通网络划分成两部分,形成网络对集,则较容易看出,此特殊子网络及其邻域,将一个接一个地交叉分布,遍及整个网络。利用这个性质,就可对网络进行充分的分解,而不丢失可行解。在上述基础上,开发出在奇网络中搜索该特殊子网络及求最大独立集的新算法,并对算法的有效性及可靠性,进行了较全面的分析。研究表明,该算法可在时间复杂性O(|V|5)界内收敛。In this paper we have analyzed the structure and characteristics of a connected network, and discovered a special kind of sub-network, which can optimize the iteration processes, and then deduced the sufficient and necessary conditions for obtaining the maximum independent set. Afterwards, we have detected that the neighborhood of this sub-network possesses the similar characters to it, but both can never be allowed incorporated together. Particularly, we have detected and identified that as you divide the network into two parts by a certain style, then transform both of them into a pair set network, where you can find that the special sub-networks and their neighborhoods appear themselves alternately distributed one by another throughout the entire pair set network. By use of this characteristic you can get the network decomposed enough without losing any solutions. All of these above have made well ready for developing a new algorithm, which will be able to search for maximum independent set in an odd network with polynomial time bound of O(|V|5).

关 键 词：奇网络对集 负包络图 广义逆向负包络图 调整搜索 剔除搜索 支撑树算法 多项式时间界 

分 类 号：O157.5[理学—数学]