Partial inverse maximum spanning tree problem under the Chebyshev norm

Xianyue Li (), Ruowang Yang, Heping Zhang and Zhao Zhang
Additional contact information
Xianyue Li: Lanzhou University
Ruowang Yang: Lanzhou University
Heping Zhang: Lanzhou University
Zhao Zhang: Zhejiang Normal University

Journal of Combinatorial Optimization, 2022, vol. 44, issue 5, No 8, 3350 pages

Abstract: Abstract Given an edge weighted graph, and an acyclic edge set, the target of the partial inverse maximum spanning tree problem (PIMST) is to get a new weight function such that the given set is included in some maximum spanning tree associated with the new function, and the difference between the two functions is minimum. In this paper, we research PIMST under the Chebyshev norm. Firstly, the definition of extreme optimal solution is introduced, and its some properties are gained. Based on these properties, a polynomial scale optimal value candidate set is obtained. Finally, strongly polynomial-time algorithms for solving this problem are proposed. Thus, the computational complexity of PIMST is completely solved.

Keywords: Partial inverse problem; Spanning tree problem; Polynomial time algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00903-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:5:d:10.1007_s10878-022-00903-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00903-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().