NETWORK DESIGN FOR MINIMUM SPANNING TREES UNDER HAMMING DISTANCE

作者：Wang, Qin; Wu, Longshu^*

来源：ANZIAM Journal, 2017, 58(3-4): 342-349.

DOI：10.1017/S1446181117000116

• network design
• spanning tree
• Hamming distance
• polynomial algorithm
• NP-hard

We consider a class of network-design problems with minimum sum of modification and network costs for minimum spanning trees under Hamming distance. By constructing three auxiliary networks, we present a strongly polynomial-time algorithm for this problem. The method can be applied to solve many network-design problems. And, we show that a variation model of this problem is NP-hard, even when the underlying network is a tree, by transforming the 0-1 knapsack problem to this model.

• 出版日期2017-4
• 单位中国计量大学