مهدی جهانگیری

اثبات ‌شده است که یافتن یک مجموعه‌ی احاطه‌گر مینیمم و در پی آن، یافتن مجموعه‌ی احاطه‌گر ‌ -kتایی برای یک گراف دلخواه عمومی، یک مساله NP-کامل است. بنابراین، روش‌هایی که برای یک گراف دلخواه در زمان معقول، تقریب مفیدی از جواب مساله را ارایه بدهند، همیشه مطلوب بوده است. در سال‌های اخیر، استفاده از رهاسازی نیمه معین در تقریب مسایل بهینه‌سازی ترکیبیاتی مورد توجه قرار گرفته است. در این مقاله، ابتدا مساله یافتن مجموعه‌ی احاطه‌گر ‌ -kتایی را به صورت یک مساله بهینه‌سازی عدد صحیح دودویی مدل‌سازی کرده و سپس یک مدل رهاسازی نیمه‌معین برای آن ارایه می‌دهیم.