【摘 要】
：
In this paper, we consider two network improvement problems with given discrete values: the inverse minimum spanning tree problem and the reverse shortest-path
【机 构】
：
Department of Mathematics,State Key Laboratory of CAD & CG
论文部分内容阅读
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.
其他文献
The genus Arthricocephalus Bergeron,1899 is revised, and Halipanktos Balker & Peel, 1997 is suggested here as a senior synonym. The subgenus Arthricocephalus (A
Some important characteristics of the atmosphere during an adiabatic process are investigated, which include the invariability of atmospheric entropy range and
The Wutai Complex associated with the adjacent Fuping and Hengshan Complexes represents the best and classical cross-section in the middle segment of the Trans-
To calculate the beam transport in the ion optical systems accurately, a beam dynamics computer program of third order approximation is developed. Many conventi
Four rock assemblages in correspondence with two different tectonic settings have been recognized in the NEE-SWW extending HP-UHP metamorphic belt in southweste
This paper presents the latest progress made on the research of Mesozoic tectonic system transition from the E-W paleoTethyan tectonic domain into NE-NNE wester
New developments in the studies of nanocomposites based on polymer matrixes and layered double hydroxides (LDHs)in recent years are reviewed combining our relat
We have studied the implementation of the Deutsch-Josza quantum algorithm in a superconducting charge-qubit quantum computer. Different from previous studies, w
This paper proposes a novel method of photorealistic simulation of Buddha Glory, a natural phenomenon of great visual beauty which can be observed in the area o
The non-quasi-Newton methods for unconstrained optimization was investigated. Non-monotone line search procedure is introduced, which is combined with the non-q