Network design for minimum spanning trees under Hamming distance
Wang, Qin ; Wu, Longshu
ANZIAM Journal, Tome 58 (2017), / Harvested from Australian Mathematical Society
Link

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

Publié le : 2017-01-01
DOI : https://doi.org/10.21914/anziamj.v58i0.11116 
@article{11116,
     title = {Network design for minimum spanning trees under Hamming distance},
     journal = {ANZIAM Journal},
     volume = {58},
     year = {2017},
     doi = {10.21914/anziamj.v58i0.11116},
     language = {EN},
     url = {http://dml.mathdoc.fr/item/11116}
}

Wang, Qin; Wu, Longshu. Network design for minimum spanning trees under Hamming distance. ANZIAM Journal, Tome 58 (2017) . doi : 10.21914/anziamj.v58i0.11116. http://gdmltest.u-ga.fr/item/11116/