Polynomial time approximation schemes for the constrained minimum spanning tree problem

Let g=(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 tree t in g such that the total weight in t is at most a given bound b. in this paper,we present two polynomial time approximation schemes (ptass) for the constrained minimum spanning tree problem. copyright © 2012 yen hung chen.