Abstract

A node (edge) ranking of a tree is a labeling of the nodes (respectively, edges) using natural numbers such that on the path between any two nodes (respectively, edges) with the same label there is an intermediate node (respectively, edge) with a higher label. A node (edge) ranking is optimal if the highest label used is as small as possible.

These problems have applications in scheduling the manufacture of complex multi-part products. A Prufer code of a labeled free tree with n nodes is a sequence of length n-2 constructed by the following sequential process: for i ranging from 1 to n-2 insert the label of the neighbor of the smallest remaining leaf into the ith position of the sequence, and then delete the leaf.

Prufer codes provide an alternative to the usual representation of trees. We’ll discuss algorithms for these problems from both sequential and parallel perspectives.