Optimal top dag compression

Abstract

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 size $O(n/{\log }_{\sigma }n)\cap O(d\cdot \log n)$, where $\sigma =\max \{2,s\}$ and $d$ is the size of the minimal dag. The size bound $O(n/{\log }_{\sigma }n)$ is optimal and improves on previous bounds.

References in corpus (1)

• Tree Compression with Top Trees Revisited

Cited by in corpus (1)

• Slowing Down Top Trees for Better Worst-Case Bounds