Scheduling the construction of value and discount weighted trees for maximum net present value

Abstract

Given a binary rooted tree in which each edge has an associated value and an associated discount factor, the problem addressed here is to determine which nodes should be visited and in what order so as to maximise the net present value calculated from the values and discount factors of the traversed edges. A process for determining which nodes to exclude is identified, some key properties of the solution are established, and an algorithm for generating an optimal sequence of nodes is presented. A key concept is the priority of a sequence of nodes, which is a certain function of the values and discount factors that determines whether the order of adjacent nodes in the sequence should be swapp..