Steiner树问题的近似算法  

APPROXIMATION ALGORITHM FOR Steiner TREE PROBLEM

作　　者：马绍汉[1] 王锐[2] 

机构地区：[1]山东大学 [2]山东海洋学院

出　　处：《计算机学报》1989年第7期558-560,共3页Chinese Journal of Computers

基　　金：国家自然科学基金

摘　　要：著名的Steiner树问题是,给定图G=(V、E),QV,在边集E上定义权函数f:E→Z^+,要求在图G上找一子树T=(Y,U),使得QY且 ∑_(c∈U)f(e)达到极小以后,我们称该问题为ST问题,R.M.Karp曾证明ST问题为NP-完全的,本文作者曾提出图上Steiner树问题:在图G=(V,E),QV上,要求一子树T=(Y,

关 键 词：STEINER树 近似算法 数据结构 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]