Network design for minimum spanning trees under Hamming distance

Qin Wang, Longshu Wu

Abstract


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.

doi:10.1017/S1446181117000116

Keywords


network design, spanning tree, Hamming distance, polynomial algorithm, NP-hard.



DOI: http://dx.doi.org/10.21914/anziamj.v58i0.11116



Remember, for most actions you have to record/upload into this online system
and then inform the editor/author via clicking on an email icon or Completion button.
ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.