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.
Fici G., Gawrychowski P. (2019). Minimal Absent Words in Rooted and Unrooted Trees. In P.S. Brisaboa N.R. (a cura di), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 152-161). Springer [10.1007/978-3-030-32686-9_11].
Minimal Absent Words in Rooted and Unrooted Trees
Fici G.
;
2019-01-01
Abstract
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Minimal Absent Words in Rooted and Unrooted Trees.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
269.95 kB
Formato
Adobe PDF
|
269.95 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
|
1907.12034.pdf
accesso aperto
Tipologia:
Post-print
Dimensione
159.45 kB
Formato
Adobe PDF
|
159.45 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
