Volume 19, Issue 2 (4-2022)                   jor 2022, 19(2): 77-91 | Back to browse issues page


XML Persian Abstract Print


Department of Applied Mathematics, Sahand University of Technology, Tabriz, Iran
Abstract:   (797 Views)
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  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.
Full-Text [PDF 962 kb]   (407 Downloads)    
Type of Study: Research | Subject: Special
Received: 2021/06/10 | Accepted: 2022/01/16

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.