

























For a metric graph $G=(V,E)$ and $R\subset V$, the internal Steiner minimum tree problem asks for a minimum weight Steiner tree spanning $R$ such that every vertex in $R$ is not a leaf. This note shows a simple polynomial-time $2ρ$-approximation algorithm, in which $ρ$ is the approximation ratio for the Steiner minimum tree problem. The result improves the previous best approximation ratio $2ρ+1$ for the problem. The ratio is not currently best but the algorithm is very simple.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。