دوره 19، شماره 2 - ( 2-1401 )                   جلد 19 شماره 2 صفحات 91-77 | برگشت به فهرست نسخه ها


XML English Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Azad Hampa B, Baroughi F. Inverse Max+Sum Spanning Tree Problem under Weighted Sum-Type Hamming Distance by Modifying the Max-Weight Vector. jor 2022; 19 (2) :77-91
URL: http://jamlu.liau.ac.ir/article-1-1911-fa.html
آزاد همپا بهاره، باروقی فهیمه. مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن‌دار نوع جمعی با اصلاح بردار وزن. تحقیق در عملیات در کاربردهای آن. 1401; 19 (2) :77-91

URL: http://jamlu.liau.ac.ir/article-1-1911-fa.html


دانشگاه صنعتی سهند، گروه ریاضی کاربردی، تبریز
چکیده:   (798 مشاهده)
مساله درخت فراگیر ماکس + سام، یک درخت فراگیرT* را در گراف G پیدا می‌کند که دارای مینیمم وزن ترکیبی max w(e)+Sum c(e)  است و در آن w(e) وزن و c(e) هزینه یالe ͼE  می‌باشند. این مساله  در زمان O(mlog n)  حل می‌شود که در آن m تعداد یال‌ها و  n تعداد رئوس گراف می‌باشد. در مساله درخت فراگیر ماکس + سام معکوس یک درخت فراگیر مفروض از گراف G که یک درخت فراگیر ماکس + سام بهینه نیست‌، در نظر گرفته می‌شود. سپس بردار وزن بهاصلاح می‌شود به‌طوری‌که درخت مفروض به یک درخت فراگیر ماکس + سام بهینه تبدیل گردد. هدف این است که هزینه تغییرات||w̅-w|| تحت فاصله همینگ مینیمم شود. در این مقاله هدف ارایه یک روش جدید برای حل مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن‌دار نوع جمعی با اصلاح بردار وزن نوع تنگنا می‌باشد‌. ابتدا مساله را فرمول‌بندی کرده و سپس یک الگوریتم ترکیبیاتی با زمان اجرای  O(mlog n)برای حل آن پیشنهاد می‌شود. در آخر یک مثال عددی برای نشان دادن کارایی روش پیشنهادی ارایه می‌شود.
متن کامل [PDF 962 kb]   (407 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: تخصصي
دریافت: 1400/3/20 | پذیرش: 1400/10/26

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
CAPTCHA

ارسال پیام به نویسنده مسئول


بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.