06063381

j

06063381 Chen, Yen Hung Polynomial time approximation schemes for the constrained minimum spanning tree problem. J. Appl. Math. 2012, Article ID 394721, 8 p. (2012). 2012 Hindawi Publishing Corporation, New York, NY EN minimum spanning tree problem polynomial time approximation schemes

doi:10.1155/2012/394721

Summary: 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 for the constrained minimum spanning tree problem.