|
|||||
|
|
| 网络分解及最大独立集算法研究(Ⅱ) | |
| 作者姓名： | 朱松年 朱嫱 |
| 作者单位： | 西南交通大学,交通运输学院,成都,610031;Geac计算机公司,Vienna,弗吉尼亚洲,22182,美国 |
| 摘 要： | 本文首先分析了一般连通网络的结构特征，发现了网络中具有优化迭代功能的特殊子网络；并对其进行了较深入的研究，提出并论证了求最大独立集的充要条件。进一步的研究发现，此特殊子网络及其邻域，具有相依、相斥的偶对性质；若按某种方式将连通网络划分成两部分，形成网络对集，则较容易看出，此特殊子网络及其邻域，将一个接一个地交叉分布，遍及整个网络．利用这个性质，就可对网络进行充分的分解，而不丢失可行解．在上述基础上，开发出在奇网络中搜索该特殊子网络及求最大独立集的新算法，并对算法的有效性及可靠性，进行了较全面的分析。研究表明，该算法可在时间复杂性O(｜V｜)界内收敛． |
| 关 键 词： | 奇网络对集 负包络图 广认逆向负包络图 调整搜索 剔除搜索 支撑树算法 多项式时间界 |
| 文章编号： | 1672-4747(2004)01-0001-11 |
| 修稿时间： | 2003-09-25 |
| 本文献已被 维普 万方数据 等数据库收录！ | |