Minimal Absent Words in Rooted and Unrooted Trees

摘要

We extend the theory of minimal absent words to (rooted and unrooted) trees, having edges labeled by letters from an alphabet Σ of cardinality σ. We show that the set MAW(T) of minimal absent words of a rooted (resp. unrooted) tree T with n nodes has cardinality O(nσ) (resp. O(n~2σ)), and we show that these bounds are realized. Then, we exhibit algorithms to compute all minimal absent words in a rooted (resp. unrooted) tree in output-sensitive time O(n + |MAW(T)|) (resp. O(n~2 + |MAW(T)|) assuming an integer alphabet of size polynomial in n.