Partial inverse min–max spanning tree problem under the weighted bottleneck hamming distance

Qingzhen Dong, Xianyue Li () and Yu Yang
Additional contact information
Qingzhen Dong: Lanzhou University
Xianyue Li: Lanzhou University
Yu Yang: Lanzhou University

Journal of Combinatorial Optimization, 2023, vol. 46, issue 4, No 5, 18 pages

Abstract: Abstract Min–max spanning tree problem is a classical problem in combinatorial optimization. Its purpose is to find a spanning tree to minimize its maximum edge in a given edge weighted graph. Given a connected graph G, an edge weight vector w and a forest F, the partial inverse min–max spanning tree problem (PIMMST) is to find a new weighted vector $$w^*$$ w ∗ , so that F can be extended into a min–max spanning tree with respect to $$w^*$$ w ∗ and the gap between w and $$w^*$$ w ∗ is minimized. In this paper, we research PIMMST under the weighted bottleneck Hamming distance. Firstly, we study PIMMST with value of optimal tree restriction, a variant of PIMMST, and show that this problem can be solved in strongly polynomial time. Then, by characterizing the properties of the value of optimal tree, we present first algorithm for PIMMST under the weighted bottleneck Hamming distance with running time $$O(|E|^2\log |E|)$$ O ( | E | 2 log | E | ) , where E is the edge set of G. Finally, by giving a necessary and sufficient condition to determine the feasible solution of this problem, we present a better algorithm for this problem with running time $$O(|E|\log |E|)$$ O ( | E | log | E | ) . Moreover, we show that these algorithms can be generalized to solve these problems with capacitated constraint.

Keywords: Partial inverse problem; Min–max spanning tree; Weighted bottleneck hamming distance; Strongly polynomial-time algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01093-8 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:46:y:2023:i:4:d:10.1007_s10878-023-01093-8

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

DOI: 10.1007/s10878-023-01093-8

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 ().