Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-25T05:25:33.574Z Has data issue: false hasContentIssue false
  • English
  • Français

NETWORK DESIGN FOR MINIMUM SPANNING TREES UNDER HAMMING DISTANCE

Published online by Cambridge University Press:  26 April 2017

QIN WANG  and
LONGSHU WU
QIN WANG
Affiliation:
College of Sciences, China Jiliang University, Hangzhou, China email [email protected]
LONGSHU WU*
Affiliation:
College of Sciences, China Jiliang University, Hangzhou, China email [email protected]
*
✉[email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

network designspanning treeHamming distancepolynomial algorithmNP-hard

MSC classification

Primary: 90C27: Combinatorial optimization
Type
Research Article
Information
The ANZIAM Journal , Volume 58 , Issue 3-4 , April 2017 , pp. 342 - 349
Copyright
© 2017 Australian Mathematical Society 

References

Burton, D., Pulleyblank, W. R. and Toint, Ph. L., “The inverse shortest paths problem with upper bounds on shortest paths costs”, in: Network optimization, Volume 450 of Lecture Notes in Economics and Mathematical Systems (Springer, Berlin–Heidelberg, 1997) 156–171.Google Scholar
Burton, D. and Toint, Ph. L., “On an instance of the inverse shortest paths problem”, Math. Program. 53 (1992) 45–61; doi:10.1007/BF01585693.Google Scholar
Diestel, R., Graph theory, 3rd edn (Springer, Heidelberg, 2005).Google Scholar
Fekete, S. P., Hochstattler, W., Kromberg, St. and Moll, Ch., “The complexity of an inverse shortest paths problem”, in: Contemporary trends in discrete mathematics, Volume 49 (American Mathematical Society, Providence, RI, 1999) 113–127.Google Scholar
Heuberger, C., “Inverse combinatorial optimization: a survey on problems, methods, and results”, J. Comb. Optim. 8 (2004) 329–361; doi:10.1023/B:JOCO.0000038914.26975.9b.Google Scholar
Korte, B. and Vygen, J., Combinatorial optimization, theory and algorithms, 4th edn (Springer, Heidelberg, 2007).Google Scholar
Wang, Q., Yuan, J. J. and Zhang, J. Z., “An inverse model for the most uniform problem”, Oper. Res. Lett. 36 (2008) 26–30; doi:10.1016/j.or1.2007.03.006.Google Scholar