گراف کامل، وزن‌دار و اقلیدسی (وزن یال‌های هر مثلث در نامساوی مثلثی صدق می‌کنند!) $G$ داده شده است. وزن راس $v$ در گراف $H$ برابر مجموع وزن یال‌های مجاور راس $v$ در $H$ می‌باشد. هدف یافتن $H$ (زیرگراف فراگیر و هم‌بندی از $G$) است که بیشینه‌ی وزن رئوسش کمینه باشد.

با فرض این‌که بزرگ‌ترین یال درخت فراگیر کمینه‌ی $G$، $\alpha$ باشد، الگوریتمی چند جمله‌ای ارائه دهید که زیر گرافی فراگیر و هم‌بند از $G$ بیابد که بیشینه‌ی وزن رئوسش حداکثر $5 \alpha$ باشد.

• سوال بعد
• سوال قبل