الگوریتم های بهینه برای مدلهای مکان یابی-p میانه ناخوشایند معکوس صحیح روی شبکه هایدرختی

در این مقاله مدل مکان یابی-p میانه ناخوشایند معکوس صحیح با p≥۲ روی شبکه درختی مورد مطالعه قرار میگیرد. در این مدل هدف تغییر افزایش یا کاهش طولهای یالی به اندازه ی صحیح با کمترین هزینه کلی با توجه به کرانه ای تغییرات داده شده است به طوری که یک مجموعه از پیش تعیین شده -pعضوی از راس های درخت با توجه به طولهای یالی جدید به مکان P-میانه ناخوشایند درخت تبدیل گردد. الگوریتمهای جواب بهینه صحیح به ترتیب با زمان اجرای شبه چندجمله ای و چند جمله ای برای مدل تحت مطالعه روی شبکه های درختی تحت نرم چبیشف و فاصله همینگ تنگنا ارائه میشود

کلیدواژه ها:

مکانیابی میانه ناخوشایند ، بهینه سازی معکوس ، بهینه سازی ترکیبیاتی ، پیچیدگی محاسباتی.