Résumé: We give a tight analysis of the greedy algorithm introduced by Krumke and Wirth for the minimum label spanning tree problem. The algorithm is shown to be a (ln(n-1)+1)-approximation for any graph with n nodes (n>1), which improves the known performance guarantee 2lnn+1.

Langue: Anglais
Index décimal 621 .Physique appliquée (électrotechnique, génie civil, génie mécanique, ingénierie appliquée, principes physiques en ingénierie)
Thème Informatique

Mots clés:
Approximation algorithms
NP-hard
Network design
Spanning tree