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

XML Persian 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-en.html
Department of Applied Mathematics, Sahand University of Technology, Tabriz, Iran
Abstract:   (430 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]   (103 Downloads)    
Type of Study: Research | Subject: Special
Received: 2021/06/10 | Accepted: 2022/01/16

Add your comments about this article : Your username or Email:

Send email to the article author

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