Developing new locality results for the Prüfer code using a remarkable linear-time decoding algorithm

Tim Paulden ; David K. Smith

The electronic journal of combinatorics, Tome 14 (2007)

Résumé

The Prüfer Code is a bijection between the $n^{n-2}$ trees on the vertex set $[1,n]$ and the $n^{n-2}$ strings in the set $[1,n]^{n-2}$ (known as Prüfer strings of order $n$). Efficient linear-time algorithms for decoding (i.e., converting string to tree) and encoding (i.e., converting tree to string) are well-known. In this paper, we examine an improved decoding algorithm (due to Cho et al.) that scans the elements of the Prüfer string in reverse order, rather than in the usual forward direction. We show that the algorithm runs in linear time without requiring additional data strutures or sorting routines, and is an 'online' algorithm — every time a new string element is read, the algorithm can correctly output an additional tree edge without any knowledge of the future composition of the string. This new decoding algorithm allows us to derive results concerning the 'locality' properties of the Prüfer Code (i.e., the effect of making small changes to a Prüfer string on the structure of the corresponding tree). First, we show that mutating the $\mu$th element of a Prüfer string (of any order) causes at most $\mu + 1$ edge-changes in the corresponding tree. We also show that randomly mutating the first element of a random Prüfer string of order $n$ causes two edge-changes in the corresponding tree with probability $2(n-3)/n(n-1)$, and one edge-change otherwise. Then, based on computer-aided enumerations, we make three conjectures concerning the locality properties of the Prüfer Code, including a formula for the probability that a random mutation to the $\mu$th element of a random Prüfer string of order $n$ causes exactly one edge-change in the corresponding tree. We show that if this formula is correct, then the probability that a random mutation to a random Prüfer string of order $n$ causes exactly one edge-change in the corresponding tree is asymptotically equal to one-third, as $n$ tends to infinity.

Détail

DOI : 10.37236/973

Classification : 94B35
Mots-clés : Prüfer code, linear time algorithms, decoding, string to tree, encoding, tree to string, decoding algorithm, random Prüfer stringrandom mutation