Polynomial time approximation schemes for the constrained minimum spanning tree problem (Q442910): Difference between revisions

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.