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: | Blum Christian |
Keywords: | heuristics, programming: dynamic |
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