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.
978-3-030-32685-2
978-3-030-32686-9
https://www.springer.com/series/558
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/387659
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact