TY - GEN
T1 - Minimal Absent Words in Rooted and Unrooted Trees
AU - Fici, Gabriele
AU - Gawrychowski, Paweł
PY - 2019
Y1 - 2019
N2 - 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 of minimal absent words of a rooted (resp. unrooted) tree T with n nodes 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 in n.
AB - 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 of minimal absent words of a rooted (resp. unrooted) tree T with n nodes 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 in n.
UR - http://hdl.handle.net/10447/387659
UR - https://www.springer.com/series/558
M3 - Conference contribution
SN - 978-3-030-32685-2; 978-3-030-32686-9
T3 - LECTURE NOTES IN ARTIFICIAL INTELLIGENCE
SP - 152
EP - 161
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -