Volume 19, Issue 2 (4-2022)
jor 2022, 19(2): 77-91 |
Back to browse issues page
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-en.html
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 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.
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
