An efficient algorithm for a capacitated subtree of a tree problem in local access telecommunication networks

An efficient algorithm for a capacitated subtree of a tree problem in local access telecommunication networks

0.00 Avg rating0 Votes
Article ID: iaor1998513
Country: United Kingdom
Volume: 24
Issue: 8
Start Page Number: 737
End Page Number: 748
Publication Date: Aug 1997
Journal: Computers and Operations Research
Authors: , ,
Keywords: programming: branch and bound, programming: dynamic, graphs
Abstract:

Given a rooted tree T with node profits and node demands, the capacitated subtree of a tree problem (CSTP) consists of finding a rooted subtree of the maximum profit, subject to having total demand no larger than the given capacity H. We first define the so-called critical item for CSTP and find upper bounds on the optimal value of CSTP in O(n2) time, where n is the number of nodes in T. We then present our branch-and-bound algorithm for solving CSTP and illustrate the algorithm by using an example. Finally, we implement our branch-and-bound algorithm by using one of the developed upper bounds and compare the computational results with those given by the branch-and-bound version of CPLEX and given by a dynamic programming algorithm for CSTP whose complexity is O(nH). The comparison shows that our branch-and-bound algorithm performs much better than both CPLEX and the dynamic programming algorithm, especially when n and H are large, for example, in the range of [50, 500] and [5000, 10,000], respectively.

Reviews

Required fields are marked *. Your email address will not be published.