计算机工程与应用Issue(10)：35-37,3.DOI:10.3778/j.issn.1002-8331.1511-0349
内部节点受限的最小生成树问题算法研究
Algorithm for minimum internal nodes constrained spanning tree problem
摘要
Abstract
The minimum internal nodes constrained spanning tree problem is considered. Give a metric graph G = ( 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 of 2 is designed and an instance is constructed to show the ratio is tight.关键词
无向赋权图/生成树/近似算法/近似比Key words
undirected weighted graph/spanning tree/approximation algorithm/performance ratio分类
数理科学引用本文复制引用
蒋小娟,张安,陈永,陈光亭..内部节点受限的最小生成树问题算法研究[J].计算机工程与应用,2017,(10):35-37,3.基金项目
国家自然科学基金(No.11571252) （No.11571252）
浙江省自然科学基金(No.LY16G010008). （No.LY16G010008）
