Solving the generalized minimum spanning tree problem with simulated annealing

Petrică C. PopCosmin SaboCorina Pop SitarMarian V. Crăciun



Full PDF


We consider a generalization of the minimum spanning tree problem, called the generalized minimum spanning tree problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present an effective algorithm for this problem. The method combines a simulated annealing algorithm (SA) with a local greedy algorithm. The heuristic that we proposed found solutions that were optimal for graphs with nodes up to 280 and were within at most 24% of optimality for larger problems, while the existing algorithms from the literature become computationally intractable.

Additional Information


Crăciun, Marian, V., Pop, Petrică, C., Sabo, Cosmin, Sitar, Corina, Pop