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

• 作者: 朱嫱 朱松年
• 来源期刊: 交通运输工程与信息学报
• 学科: 数学
• 关键词: 奇网络对集 负包络图 广认逆向负包络图 调整搜索 剔除搜索 支撑树算法 多项式时间界
• 年，卷（期）: 2004,（1）
• 页码范围: 1-11
• 页数: 11页
• 分类号: O157.5
• 字数: 11655字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-4747.2004.01.001

摘要

本文首先分析了一般连通网络的结构特征,发现了网络中具有优化迭代功能的特殊子网络;并对其进行了较深入的研究,提出并论证了求最大独立集的充要条件.进一步的研究发现,此物殊子网络及其邻域,具有相依、相斥的偶对性质;若按某种方式将连通网络划分成两部分,形成网络对集,则较容易看出,此特殊子网络及其邻域,将一个接一个地交叉分布,遍及整个网络,利用这个性质,就可对网络进行充分的分解,而不丢失可行解.在上述基础上,开发在奇网络中搜索该特殊子网络及求最大独立集的新算法,并对算法的有效性及可靠性,进行了较全面的分析.研究表明,该算法可在时间复杂性O(|V|5)界内收敛.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱松年	西南交通大学交通运输学院	5	135	4.0	5.0