Minimal Absent Words in Rooted and Unrooted Trees

Minimal Absent Words in Rooted and Unrooted Trees
复制标题

有根树和无根树中的缺失词最少

DOI：
10.1007/978-3-030-32686-9_11
复制
发表时间：
2019
期刊：
ArXiv
影响因子：
--
通讯作者：
Paweł Gawrychowski
Paweł Gawrychowski
中科院分区：
--
文献类型：
--
作者：
G. Fici;Paweł Gawrychowski

文献摘要

被引文献

相似文献

我们将最小缺失词的理论扩展到(有根和无根)树，树的边由基数字母标出。我们证明了有根(无根)树的最小缺席词集有基数(分别为)，并证明了这些界是可实现的。然后，我们给出了在输出敏感时间内(假设大小为多项式inn的整数字母表)计算有根(分别为无根)树中所有最小缺失词的算法。
We extend the theory of minimal absent words to (rooted and unrooted) trees, having edges labeled by letters from an alphabetof cardinality. We show that the setof minimal absent words of a rooted (resp. unrooted) treeTwithnnodes has cardinality(resp.), 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(resp.assuming an integer alphabet of size polynomial inn.