Language:

Inverse max+sum spanning tree problem under weighted [Formula omitted] norm by modifying max-weight vector

Journal of global optimization, 2022-11, Vol.84 (3), p.715 [Peer Reviewed Journal]

Full text available

Citations Cited by

Title:
Inverse max+sum spanning tree problem under weighted [Formula omitted] norm by modifying max-weight vector
Author: Jia, Junhua ; Guan, Xiucui ; Zhang, Qiao ; Qian, Xinqiang ; Pardalos, Panos M
Subjects: Algorithms
Is Part Of: Journal of global optimization, 2022-11, Vol.84 (3), p.715
Description: The max+sum spanning tree (MSST) problem is to determine a spanning tree T whose combined weight [Formula omitted] is minimum for a given edge-weighted undirected network G(V, E, c, w). This problem can be solved within [Formula omitted] time, where m and n are the numbers of edges and nodes, respectively. An inverse MSST problem (IMSST) aims to determine a new weight vector [Formula omitted] so that a given [Formula omitted] becomes an optimal MSST of the new network [Formula omitted]. The IMSST problem under weighted [Formula omitted] norm is to minimize the modification cost [Formula omitted], where q(e) is a cost modifying the weight w(e). We first provide some optimality conditions of the problem. Then we propose a strongly polynomial time algorithm in [Formula omitted] time based on a binary search and a greedy method. There are O(m) iterations and we solve an MSST problem under a new weight in each iteration. Finally, we perform some numerical experiments to show the efficiency of the algorithm.
Publisher: Springer
Language: English
Identifier: ISSN: 0925-5001
EISSN: 1573-2916
DOI: 10.1007/s10898-022-01170-y
Source: ProQuest Central

Back to results list

Previous Result 4 Next Go to Next page


INSPIRE LIBRARY - TON DUC THANG UNIVERSITY	(84-028) 37 755 057	Feedback
19 Nguyen Huu Tho St. Dist.7, HCM	thuvien@tdtu.edu.vn	Feedback

Searching Remote Databases, Please Wait