ملخص: 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.

لغة: إنجليزية
الفهرس العشري 621 .الفيزياء التطبيقية (الهندسة الكهربائية ، الهندسة المدنية ، الهندسة الميكانيكية ، الهندسة التطبيقية ، المبادئ الفيزيائية في الهندسة)
الموضوع الإعلام الآلي

الكلمات الدالة:
Approximation algorithms
NP-hard
Network design
Spanning tree