The Profile Minimization Problem in Trees
David Li-Wei Kuo, Gerard J. Chang · SIAM Journal on Computing · 1994
The profile minimization problem is to find a one-to-one function f from the vertex set $V(G)$ of a graph G to the set of all positive integers such that $\sum _{x \in V(G)} \{ f(x) - \min _{y \in N[x]} f(y)\} $ is as small as possible, where $N[x] = \{ x\} \cup \{ y:y{\text{ is adjacent }}x \} $ is the closed neighborhood of x in G. This paper gives an $O(n^{1.722} )$ time algorithm for the problem in a tree of n vertices.