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) 

刊 名： 自然科學(xué)進(jìn)展（英文版）  SCI 英文刊名： PROGRESS IN NATURAL SCIENCE  年，卷(期)： 2006 16(6)  分類號(hào)： N1  關(guān)鍵詞： minimum spanning tree   shortest-path problem   inverse problem   reverse problem   computational complexity  

【Inverse minimum spanning tree proble】相關(guān)文章：

My family tree作文（通用20篇）10-18

初中英語作文：種樹 Plant a Tree（精選13篇）11-02

第15講：fly off the handle; bark up the wrong tree05-04