任意无向加权图K点连通扩充的逐次改善算法

• 作者: 孙雨耕 王永德
• 来源期刊: 辽宁工程技术大学学报(自然科学版)
• 学科: 工学
• 关键词: 无向加权图 K点连通 扩充 算法 边交换
• 年，卷（期）: 2008,（1）
• 所属期刊栏目: 电气工程与计算机技术
• 页码范围: 82-84
• 页数: 3页
• 分类号: TN915
• 字数: 1910字
• 语种: 中文
• DOI: 10.3969/j.issn.1008-0562.2008.01.025

摘要

为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K 点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明.最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果.为解决任意无向加权图最小扩充问题给出了一种新途径.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙雨耕	天津大学电气与自动化工程学院	85	1497	20.0	36.0
2	王永德	青岛理工大学自动化工程学院	10	25	3.0	4.0