Optimal labellings of rooted directed trees (Q1271877)

Let \(D=(V,E)\) be an uncyclic directed graph with exactly one vertex of outdegree \(0\), i.e. \(D\) is a rooted directed tree (RDT). The author studies a labelling problem for RDT that arised in scheduling theory. Consider a bijection \(\phi:E\to \{1,2,\dots,| E| \}\) such that \(d_{\phi}(e)=\phi(v)-\phi(u)>0\) for any arc \((u,v)\). It can easily be shown that such a bijection always exists. The problem is to find a bijection such that \(d_{\phi}(D)=\sum_{e\in E} d_{\phi}(e)\) is minimum among all feasible bijections. The author proves several necessary, and necessary and sufficient conditions for a bijection to be optimal, and provides an algorithm of complexity \(O(n^3)\) for finding an optimal one.