内部节点受限的最小生成树问题算法研究  

Algorithm for minimum internal nodes constrained spanning tree problem

作　　者：蒋小娟[1] 张安[1] 陈永[1] 陈光亭[2] JIANG Xiaojuan;ZHANG An;CHEN Yong;CHEN Guangting(School of Science, Hangzhou Dianzi University, Hangzhou 310018, China;Taizhou University, Taizhou, Zhejiang 317000, China)

机构地区：[1]杭州电子科技大学理学院,杭州310018 [2]台州学院,浙江台州317000

出　　处：《计算机工程与应用》2017年第10期35-37,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(No.11571252);浙江省自然科学基金(No.LY16G010008)

摘　　要：研究内部节点受限的最小生成树问题:给定一个赋权无向完全图G=(V,E),假定w:E→R^+为边集E的权重函数且满足三角不等式,给定点集V的一个子集R(RV),目标是寻找图G的一个满足R中的点皆为内部顶点的权重最小的生成树。由于该问题是NP-困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。The minimum internal nodes constrained spanning tree problem is considered.Give a metric graph G=(V,E)with a cost function w:E→R+and one subset R of V(R?V),the minimum internal nodes constrained spanning tree problem asks for a minimum weight spanning tree such that every vertex in R is not a leaf.As the problem is NP-hard,a Pseudo-polynomial time optimal algorithm is first provided,then a simple polynomial time approximation algorithm with a performance ratio of2is designed and an instance is constructed to show the ratio is tight.

关 键 词：无向赋权图 生成树 近似算法 近似比 

分 类 号：O224[理学—运筹学与控制论]