Polynomial Time Approximation Schemes for the Constrained MinimumSpanning Tree Problem

Abstract EN

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.