steiner树问题的近似算法

摘要

cqvip:著名的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,