Approximation results for the generalized minimum spanning tree problem


Petrică Claudiu Pop


Abstract

carpathian_2002_18_095_104_abstract

Full PDF

carpathian_2002_18_095_104

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

Author(s)

Pop, Petrică Claudiu