Optimal top dag compression

Markus Lohrey, Carl Philipp Reh, Kurt Sieber

It is shown that for a given ordered node-labelled tree of size $n$ and with $s$ many different node labels, one can construct in linear time a top dag of height $O(\log n)$ and si…