English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Prufer 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 Prufer 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 Prufer 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 Prufer Code (i.e., the effect of making small changes to a Prufer string on the structure of the corresponding tree). First, we show that mutating the $\mu$th element of a Prufer 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 Prufer 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 Prufer Code, including a formula for the probability that a random mutation to the $\mu$th element of a random Prufer 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 Prufer string of order $n$ causes exactly one edge-change in the corresponding tree is asymptotically equal to one-third, as $n$ tends to infinity.

Developing New Locality Results for the Prüfer Code using a Remarkable Linear-Time Decoding Algorithm