Title :
Parallel savings heuristics for designing multi-center tree networks
Author :
Altinkemer, Kemal
Author_Institution :
Krannert Graduate Sch. of Manage., Purdue Univ., West Lafayette, IN, USA
Abstract :
Parallel savings heuristics are presented for the multicenter tree-network design problem, where the objective is to find the least cost connection between a given set of user and backbone nodes (centers). Each subtree has to satisfy the capacity restriction of the backbone nodes. This approach combines the savings method with the matching problem, and is compared to L.R. Esau and K.C. Williams´ (1966) heuristic modified to handle the multicenter case. This parallel savings heuristic allows one to decide how many backbone nodes to open and how to connect the user nodes to these backbone nodes. The performance of the parallel savings algorithms is demonstrated on a very large set of test problems
Keywords :
computer networks; parallel algorithms; trees (mathematics); backbone nodes; capacity restriction; least cost connection; multi-center capacitated network design; multicenter tree-network design problem; parallel savings heuristic; user nodes; Accelerated aging; Bones; Communication networks; Computer network reliability; Computer networks; Costs; Data communication; Intelligent networks; Spine; Testing;
Conference_Titel :
System Sciences, 1989. Vol.III: Decision Support and Knowledge Based Systems Track, Proceedings of the Twenty-Second Annual Hawaii International Conference on
Conference_Location :
Kailua-Kona, HI
Print_ISBN :
0-8186-1913-9
DOI :
10.1109/HICSS.1989.49195
