A priority queue transforms an input permutation $\sigma $ of some set of size n into an output permutation $\tau $ The set $R_n $ of such related pairs $(\sigma ,\tau )$ is studied. Efficient algorithms for determining $s(\tau ) = |\sigma :(\sigma ,\tau ) \in R_n |$, and $t(\sigma ) = |\tau :(\sigma ,\tau ) \in R_n |$ are given, a new proof that $|R_n | = (n + 1)^{n - 1} $ is given, and the transitive closure of $R_n $ is found.

An efficient algorithm is given for generating uniformly at random a rooted tree with a specified number of nodes of each degree. The algorithm requires linear time, needs hardly any auxiliary storage and uses only very simple operations.

M.D. Atkinson, J.S. Heslop-Harrison; A simple method of hidden-line removal in three-dimensional modelling: hiding the problem behind filled polygons, Bioi

The problem of assigningncarrier frequencies so as to avoid certain types (third and fifth order) of intermodulation interference is discussed. For the third-order case, close upper and lower bounds on the optimal solution are established; and close to optimal solutions are given forn < 100(previously, suboptimal solutions were known only forn \leq 23). For the fifth-order case, it is shown that some existing results can be applied to this problem, and suboptimal solutions obtained by this construction are given forn \leq 17(no solutions were known previously).

It is shown that there is essentially only one $m \times n \times (mn - 2)$ tensor of rank $mn - 1$. It is also proved that, except for this tensor, all $m \times n \times p$ tensors with $p \leqq mn - 2$ have rank at most $mn - 2$. The main tool is Kronecker’s theory of matrix pencils which has already been applied directly by Ja’Ja’ [SIAM J. Comput., 8 (1979), pp. 443–462] to study the ranks of $m \times n \times 2$ tensors. We show that each nondegenerate $m \times n \times (mn - 2)$ tensor is determined by a related $m \times n \times 2$ tensor and apply the Kronecker theory to this related tensor.