Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-25T06:00:04.428Z Has data issue: false hasContentIssue false
  • English
  • Français

COMPUTATIONAL METHODS FOR LOGISTICS PROBLEMS RELATED TO OPTIMAL TREES

Published online by Cambridge University Press:  07 March 2017

LONGSHU WU ,
QIN WANG  and
XIAOBING YANG
LONGSHU WU
Affiliation:
College of Sciences, China Jiliang University, Hangzhou, China email [email protected], [email protected], [email protected]
QIN WANG*
Affiliation:
College of Sciences, China Jiliang University, Hangzhou, China email [email protected], [email protected], [email protected]
XIAOBING YANG
Affiliation:
College of Sciences, China Jiliang University, Hangzhou, China email [email protected], [email protected], [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.

In recent years, balanced network optimization problems play an important role in practice, especially in information transmission, industry production and logistics management. In this paper, we consider some logistics optimization problems related to the optimal tree structures in a network. We show that the most optimal subtree problem is NP-hard by transforming the connected dominating set problem into this model. By constructing the network models of the most balanced spanning tree problem with edge set restrictions, and by finding the optimal subtrees in special networks, we present efficient computational methods for solving some logistics problems.

Keywords

computational methodspanning treepolynomial algorithmnondeterministic polynomial-time (NP)-hard

MSC classification

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

References

Buchheim, C. and Klein, L., “Combinatorial optimization with one quadratic term: spanning trees and forests”, Discrete Appl. Math. 177 (2014) 34–52; doi:10.1016/j.dam.2014.05.031.Google Scholar
Camerini, P. M., Maffioli, F., Martello, S. and Toth, P., “Most and least uniform spanning trees”, Discrete Appl. Math. 15 (1986) 181–197; doi:10.1016/0166-218X(86)90041-7.Google Scholar
Charkhgard, H. and Savelsbergh, M., “Efficient algorithms for traveling salesman problems arising in warehouse order picking”, ANZIAM J. 57 (2015) 166–174; doi:10.1017/S1446181115000140.Google Scholar
Galil, Z. and Schieber, B., “On finding most uniform spanning trees”, Discrete Appl. Math. 20 (1988) 173–175; doi:10.1016/0166-218X(88)90062-5.Google Scholar
Korte, B. and Vygen, J., Combinatorial optimization, theory and algorithms, 4th edn (Springer, Heidelberg, 2007).Google Scholar
Kundu, S. and Majumder, S., “A linear time algorithm for optimal $k$ -hop dominating set of a tree”, Inform. Process. Lett. 116 (2016) 197–202; doi:10.1016/j.ipl.2015.07.014.CrossRefGoogle Scholar
Murmu, M. K., “A distributed approach to construct minimum spanning tree in cognitive radio networks”, Procedia Comput. Sci. 70 (2015) 166–173; doi:/10.1016/j.procs.2015.10.066.CrossRefGoogle Scholar
Punnen, A. P. and Nair, K. P. K., “Constrained balanced optimization problems”, Comput. Math. Appl. 37 (1999) 157–163; doi:10.1016/S0898-1221(99)00119-4.Google Scholar
Shiono, N. and Suzuki, H., “Optimal pipe-sizing problem of tree-shaped gas distribution networks”, European J. Oper. Res. 252 (2016) 550–560; doi:10.1016/j.ejor.2016.01.008.Google Scholar
Wang, F., Xie, Z. and Liang, Z. J., “Minimal balanced degree spanning tree with edge set restricted problem”, Math. Theory Appl. 24 (2004) 100–103; http://en.cnki.com.cn/Article_en/CJFDTotal-LLYY200402022.htm.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