计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (10): 35-37.DOI: 10.3778/j.issn.1002-8331.1511-0349

• 理论与研发 • 上一篇    下一篇

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

蒋小娟1,张  安1,陈  永1,陈光亭2   

  1. 1.杭州电子科技大学 理学院,杭州 310018
    2.台州学院,浙江 台州 317000
  • 出版日期:2017-05-15 发布日期:2017-05-31

Algorithm for minimum internal nodes constrained spanning tree problem

JIANG Xiaojuan1, ZHANG An1, CHEN Yong1, CHEN Guangting2   

  1. 1.School of Science, Hangzhou Dianzi University, Hangzhou 310018, China
    2.Taizhou University, Taizhou, Zhejiang 317000, China
  • Online:2017-05-15 Published:2017-05-31

摘要: 研究内部节点受限的最小生成树问题:给定一个赋权无向完全图[G=V,E],假定[w:E→R+]为边集[E]的权重函数且满足三角不等式,给定点集[V]的一个子集[RR?V],目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小的生成树。由于该问题是[NP-]困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。

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

Abstract: 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 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