Revisiting dynamic programming for finding optimal subtrees in trees

Revisiting dynamic programming for finding optimal subtrees in trees

0.00 Avg rating0 Votes
Article ID: iaor20084619
Country: Netherlands
Volume: 177
Issue: 1
Start Page Number: 102
End Page Number: 115
Publication Date: Feb 2007
Journal: European Journal of Operational Research
Authors:
Keywords: heuristics, programming: dynamic
Abstract:

In this paper we revisit an existing dynamic programming algorithm for finding optimal subtrees in edge weighted trees. This algorithm was sketched by Maffioli in a technical report in 1991. First, we adapt this algorithm for the application to trees that can have both node and edge weights. Second, we extend the algorithm such that it does not only deliver the values of optimal trees, but also the trees themselves. Finally, we use our extended algorithm for developing heuristics for the k-cardinality tree problem in undirected graphs G with node and edge weights. This NP-hard problem consists of finding in the given graph a tree with exactly k edges such that the sum of the node and the edge weights is minimal. In order to show the usefulness of our heuristics we conduct an extensive computational analysis that concerns most of the existing problem instances. Our results show that with growing problem size the proposed heuristics reach the performance of state-of-the-art metaheuristics. Therefore, this study can be seen as a cautious note on the scaling of metaheuristics.

Reviews

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