Polynomial Time Approximation Schemes for the Constrained MinimumSpanning Tree Problem
Yen Hung Chen · Journal of Applied Mathematics · 2012
LetG= (V,E) be an undirected graph with a weight function and a cost function on edges. The constrained minimum spanning tree problem is to find a minimum cost spanning treeTinGsuch that the total weight inTis at most a given boundB. In this paper, we present two polynomial time approximation schemes (PTASs) for the constrained minimum spanning tree problem.