فهرست نشریات علمی دسترسی آزاد ایران

The capacitated minimum spanning tree problem (CMSTP), a well-known combinatorial optimiza-tion problem, holds a central place in telecommunication network design. This problem is to find a minimumcost spanning tree with an extra cardinality limitation on the orders of the subtrees incident to a certain rootnode. The balanced capacitated minimum spanning tree problem (BCMSTP) is a special case that aims to balance the orders of the subtrees. We show this problem is NP-hard and present two approximation algorithms,in this paper.Considering the maximum order of the subtrees Q, we provide a (3 - 1/Q)-approximation algorithm to find abalanced solution. We improve this result to a (2:5 + \epsilon)-approximation algorithm (for every given \epsilon > 0), inthe 2d-Euclidean spaces. Also, we present a polynomial time approximation scheme (PTAS) for CMSTP.