مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن‌دار نوع جمعی با اصلاح بردار وزن

مساله درخت فراگیر ماکس + سام، یک درخت فراگیرt* را در گراف g پیدا می کند که دارای مینیمم وزن ترکیبی max w(e)+σ c(e) است و در آن w(e) وزن و c(e) هزینه یالe ͼe می باشند. این مساله در زمان o(m logn) حل می شود که در آن m تعداد یال ها و n تعداد رئوس گراف می باشد. در مساله درخت فراگیر ماکس + سام معکوس یک درخت فراگیر مفروض از گراف g که یک درخت فراگیر ماکس + سام بهینه نیست ، در نظر گرفته می شود. سپس بردار وزن wبه w̅ اصلاح می شود به طوری که درخت مفروض به یک درخت فراگیر ماکس + سام بهینه تبدیل گردد. هدف این است که هزینه تغییرات||w̅-w|| تحت فاصله همینگ مینیمم شود. در این مقاله هدف ارایه یک روش جدید برای حل مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن دار نوع جمعی با اصلاح بردار وزن نوع تنگنا می باشد . ابتدا مساله را فرمول بندی کرده و سپس یک الگوریتم ترکیبیاتی با زمان اجرای o(mlogn)برای حل آن پیشنهاد می شود. در آخر یک مثال عددی برای نشان دادن کارایی روش پیشنهادی ارایه می شود.

Inverse Max+Sum Spanning Tree Problem under Weighted Sum-Type Hamming Distance by Modifying the Max-Weight Vector

The max+sum spanning tree problem is to find a spanning tree T* which makes the combined  weight “max w(e)+Sum c(e) time” as small as possible, in which a weight w(e) and a cost c(e) are prescribed for each e ͼT. The problem can be solved in O(mlog n)  time. In an inverse max+sum spanning tree problem, T0 is a given spanning tree of G, which is not an optimal max+sum spanning tree. Then we modify the weight vector w to w̅ so that T0 becomes a max+sum spanning tree. The goal is to minimize the modification cost ||w̅-w||under Hamming distance. This paper presents a new solution algorithm for the inverse max+sum spanning tree problem under weighted sum-type Hamming distance  by modifying the max-weight vector with time complexity of O(mlog n) . First, we formulate the problem and then present a new solution algorithm for the problem under investigation. Finally, we present a numerical example to illustrate the efficiency of the algorithm.