Optimal top dag compression

12/15/2017

∙

by   Markus Lohrey, et al.

∙

0

∙

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.