An Efficient Node Partitioning Algorithm for the Capacitated Minimum Spanning Tree Problem

Melbourne, Australia July 11-July 13

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/ICIS.2007.56

6th IEEE/ACIS International Conferenc ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Jun Han Articles by Zhaohao Sun Articles by Jinpeng Huai Articles by Xian Li

	ASCII Text	x
	Jun Han, Zhaohao Sun, Jinpeng Huai, Xian Li, "An Efficient Node Partitioning Algorithm for the Capacitated Minimum Spanning Tree Problem," Computer and Information Science, ACIS International Conference on, pp. 575-580, 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007), 2007.

	BibTex	x
	@article{ 10.1109/ICIS.2007.56, author = {Jun Han and Zhaohao Sun and Jinpeng Huai and Xian Li}, title = {An Efficient Node Partitioning Algorithm for the Capacitated Minimum Spanning Tree Problem}, journal ={Computer and Information Science, ACIS International Conference on}, volume = {0}, year = {2007}, isbn = {0-7695-2841-4}, pages = {575-580}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICIS.2007.56}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computer and Information Science, ACIS International Conference on TI - An Efficient Node Partitioning Algorithm for the Capacitated Minimum Spanning Tree Problem SN - 0-7695-2841-4 SP575 EP580 A1 - Jun Han, A1 - Zhaohao Sun, A1 - Jinpeng Huai, A1 - Xian Li, PY - 2007 KW - Branch and bound; Search tree; Pruning; Neighborhood search; Partition VL - 0 JA - Computer and Information Science, ACIS International Conference on ER -

Jun Han, Beihang University, China

Zhaohao Sun, University of Wollongong, Australia

Jinpeng Huai, Beihang University, China

Xian Li, Beihang University, China

This paper studies the capacitated minimum spanning tree (CMST) problem, which is one of the most fundamental and significant problems in the optimal design of communication networks. A solution method using combined neighborhood search and branch and bound technique is introduced and its performance is presented. The advantage of the algorithm is shown while the process of searching for the optimal solution is illustrated. Computational experiences demonstrate that the proposed strategy significantly improves the efficiency of the previous node-orientated branch and bound algorithm.

Index Terms:

Branch and bound; Search tree; Pruning; Neighborhood search; Partition

Citation:

Jun Han, Zhaohao Sun, Jinpeng Huai, Xian Li, "An Efficient Node Partitioning Algorithm for the Capacitated Minimum Spanning Tree Problem," icis, pp.575-580, 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007), 2007

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.