网络分解及最大独立集算法研究（Ⅱ）

• 作 者: 朱松年 朱嫱
• 机 构: 西南交通大学交通运输学院,Geac计算机公司
• 出 处: 交通运输工程与信息学报
• 发表日期: 2003年2期
• 关键词: 奇网络对集 负包络图 广义逆向负包络图 调整搜索 剔除搜索 支撑树算法 多项式时间界 odd pair-sets network negative envel

本文首先分析了一般网络的结构特征，开发出对任意网络进行变换及分解、且不丢失可行解的新方法，继而发现了网络中具有优化迭代功能的特殊子网络；对其进行了较深入的研究，提出并论证了求最大独立集的充要条件：研制出在网络中系统搜索该特殊子网络的新算法。最后，对算法的有效性及可靠性，进行了较全面的分析论证，研究表明，该算法可在时间复杂性O(|V|^5)界内收敛。