- 相关推荐
Inverse minimum spanning tree problem and reverse shortest-path problem with discrete values
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.
作 者： LIU Longcheng HE Yong 作者单位： LIU Longcheng(Department of Mathematics, Zhejiang University, Hangzhou 310027,China)HE Yong(State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027, China)
刊 名： 自然科学进展（英文版） SCI 英文刊名： PROGRESS IN NATURAL SCIENCE 年，卷(期)： 2006 16(6) 分类号： N1 关键词： minimum spanning tree shortest-path problem inverse problem reverse problem computational complexity【Inverse minimum spanning tree proble】相关文章：