String Covers of a Tree

Abstract

We consider covering labeled trees by a collection of paths with the same string label, called a (string) cover of a tree. We show how to compute all covers of a directed (rooted) labeled tree in $O(n\log n/\log \log n)$ time and all covers of an undirected labeled tree in $O(n^2)$ time and space or in $O(n^2\log n)$ time and $O(n)$ space. We also show several essential differences between covers in standard strings and covers in trees.