On Scheduling the Construction of a Tree

A schedule of a tree T = (V, E) of n edges is a one-to-one function α: {1, 2, …, n}→E. The problem of finding an optimal schedule of a tree is discussed in this chapter. This problem has an application in the construction of tree-like communication networks where the internal vertices require expensive transmission equipment (e.g., a directory). The cost of a schedule is linear with the total hiring cost of the transmission equipment during the construction process, assuming each edge is constructed in one unit of time.