Inverse minimum spanning tree problem and reverse shortest-path problem with discrete values*
Longcheng Liu, Yong Min He · Progress in Natural Science Materials International · 2006
Abstract In this paper, we consider two network improvement problems with given discrete values: the inverse minimum spanning tree problem and the reverse shortest-path problem, where the decrements of the weight of the edges are given discrete values. First for the three models of the inverse minimum spanning tree problem (the sum-type, the bottleneck-type and the constrained bottlenecktype), we present their respective strongly polynomial algorithms. Then, we show that the reverse shortest-path problem is strongly NP-complete. Supported by National Science Foundation of China (Grant No. 60021201)