دوره 19، شماره 2 - ( 2-1401 )
جلد 19 شماره 2 صفحات 91-77 |
برگشت به فهرست نسخه ها
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
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
URL: http://jamlu.liau.ac.ir/article-1-1911-fa.html
آزاد همپا بهاره، باروقی فهیمه. مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن‌دار نوع جمعی با اصلاح بردار وزن. تحقیق در عملیات در کاربردهای آن 1401; 19 (2) :91-77
دانشگاه صنعتی سهند، گروه ریاضی کاربردی، تبریز
چکیده: (429 مشاهده)
مساله درخت فراگیر ماکس + سام، یک درخت فراگیرT* را در گراف G پیدا می‌کند که دارای مینیمم وزن ترکیبی max w(e)+Sum c(e) است و در آن w(e) وزن و c(e) هزینه یالe ͼE می‌باشند. این مساله در زمان O(mlog n) حل می‌شود که در آن m تعداد یال‌ها و n تعداد رئوس گراف می‌باشد. در مساله درخت فراگیر ماکس + سام معکوس یک درخت فراگیر مفروض از گراف G که یک درخت فراگیر ماکس + سام بهینه نیست، در نظر گرفته می‌شود. سپس بردار وزنw به w̅ اصلاح می‌شود به‌طوری‌که درخت مفروض به یک درخت فراگیر ماکس + سام بهینه تبدیل گردد. هدف این است که هزینه تغییرات||w̅-w|| تحت فاصله همینگ مینیمم شود. در این مقاله هدف ارایه یک روش جدید برای حل مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن‌دار نوع جمعی با اصلاح بردار وزن نوع تنگنا می‌باشد. ابتدا مساله را فرمول‌بندی کرده و سپس یک الگوریتم ترکیبیاتی با زمان اجرای O(mlog n)برای حل آن پیشنهاد می‌شود. در آخر یک مثال عددی برای نشان دادن کارایی روش پیشنهادی ارایه می‌شود.
ارسال پیام به نویسنده مسئول
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |
