Capacitated partial inverse maximum spanning tree under the weighted Hamming distance

Xianyue Li (), Xichao Shu, Huijing Huang and Jingjing Bai
Additional contact information
Xianyue Li: Lanzhou University
Xichao Shu: Lanzhou University
Huijing Huang: Lanzhou University
Jingjing Bai: Lanzhou University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 4, No 2, 1005-1018

Abstract: Abstract Given an edge weighted graph, and an acyclic edge set, the goal of partial inverse maximum spanning tree problem is to modify the weight function as little as possible such that there exists a maximum spanning tree with respect to the new weight function containing the given edge set. In this paper, we consider this problem with capacitated constraint under the weighted Hamming distance. Under the weighted sum Hamming distance, if the given edge set has at least two edges, we show that this problem is APX-Hard even without the capacitated constraint; if the given edge set contains only one edge, we present a strongly polynomial time algorithm to solve it. Under the weighted bottleneck Hamming distance, we present an algorithm with time complexity $$O(m\log ^2 m)$$ O ( m log 2 m ) , where m is the number of edges of the given graph.

Keywords: Partial inverse combinatorial optimization problem; Spanning tree; Hamming distance; Computational complexity (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00433-x 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:38:y:2019:i:4:d:10.1007_s10878-019-00433-x

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

DOI: 10.1007/s10878-019-00433-x

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