基于含连通图约束的背包问题的图分割方法

• 作者: 吴鹏 徐兴伟 李胜文 林济铿 王旭东 邵广惠 马新
• 来源期刊: 中国电机工程学报
• 学科: 工学
• 关键词: 图分割 含连通图约束的背包问题 含图约束的背包问题 近似算法 电力系统最优主动解列
• 年，卷（期）: 2012,（10）
• 页码范围: 134-141
• 分类号: TM71
• 字数: 7623字
• 语种: 中文

摘要

图分割技术(网络分割技术)在互联网研究、交通运输、电网故障诊断和电力系统解列等方面有着重要的意义.首次建立一个新的图分割问题——含连通图约束的背包问题(connected graph constrained knapsack problem,CGKP),并提出其有效近似算法.引入与图连通性相关的4个新节点集合,证明这些新节点集合的性质,并提出这些节点集合的搜索方法;结合新节点集合的性质及搜索算法,通过对含图约束的背包问题近似算法进行扩展,提出求解 CGKP 的近似算法,并讨论此算法的计算复杂性.算例结果证明了该算法的有效性.因电力系统主动最优解列问题在一定条件下可归结为一个 CGKP,该研究成果为电力系统最优主动解列断面搜索问题的求解奠定了理论基础.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐兴伟		9	209	6.0	9.0
2	邵广惠		5	105	4.0	5.0
3	林济铿		2	42	2.0	2.0
4	王旭东	天津市电力公司技术中心	6	114	5.0	6.0
5	李胜文		1	26	1.0	1.0
6	吴鹏		2	42	2.0	2.0
7	马新		2	68	2.0	2.0