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

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

作　　者：朱松年[1] 朱嫱 

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

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

摘　　要：本文首先分析了一般网络的结构特征,开发出对任意网络进行变换及分解、且不丢失可行解的新方法。继而发现了网络中具有优化迭代功能的特殊子网络;对其进行了较深入的研究,提出并论证了求最大独立集的充要条件;研制出在网络中系统搜索该特殊子网络的新算法。最后,对算法的有效性及可靠性,进行了较全面的分析论证。研究表明,该算法可在时间复杂性O(|V|5)界内收敛。This paper has analyzed the structure and characteristics of a general network and developed a new approach to transform and decompose arbitrary networks without losing any feasible solutions. We have identified a special kind of sub-network that can optimize iteration processes, and presents the sufficient and necessary conditions for obtaining the maximum independent set. Consequently, we have developed a new algorithm for finding the spanning tree of such a special sub-network in a general network, and proved its converging efficiency and reli-ablity with polynomial time bound O(|V|5).

关 键 词：网络分解 结构特征 最大独立集 算法 时间复杂性 迭代效果 偶网络 

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