标题:Steiner树问题的近似算法
作者:马绍汉,王锐
作者机构:[马绍汉,王锐]山东大学,山东海洋学院
来源:计算机学报
出版年:1989
期:07
页码:558-560
关键词:近似算法;ST;定理;Steiner;顶点集;
摘要: 著名的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
资源类型:期刊论文
原文链接:http://kns.cnki.net/kns/detail/detail.aspx?FileName=JSJX198907011&DbName=CJFQ1989
TOP