Optimal top dag compression
share
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( n) and size O(n / _σ n) ∩ O(d · n), where σ = { 2, s} and d is the size of the minimal dag. The size bound O(n / _σ n) is optimal and improves on previous bounds.
READ FULL TEXT