Approximation results for the generalized minimum spanning tree problem

Petrică Claudiu Pop



Full PDF


We consider the Generalized Minimum Spanning Tree problem denoted by GMST. It is known that the GMST problem is NP-hard. Throughout this paper we distinguish between so-called positive results and negative in the area of approximation theory. We present an in-approximability result for the GMST problem and under special assumptions we give an approximation algorithm for the problem.

Additional Information


Pop, Petrică Claudiu