Archivio istituzionale della ricerca dell'Università degli Studi di Palermo
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, pubblicazioni, progetti, attività) adottato dall’Università di Palermo, e ha lo scopo di raccogliere, conservare, documentare, e diffondere ad accesso aperto le informazioni relative alla produzione scientifica degli autori afferenti all’Ateneo.
EnglishWe 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].
| Data di pubblicazione: | 2019 | |
| Titolo: | Minimal Absent Words in Rooted and Unrooted Trees | |
| Autori: | ||
| Citazione: | 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]. | |
| 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. | |
| URL: | https://www.springer.com/series/558 | |
| ISBN: | 978-3-030-32685-2 978-3-030-32686-9 | |
| Digital Object Identifier (DOI): | 10.1007/978-3-030-32686-9_11 | |
| Appare nelle tipologie: | 2.07 Contributo in atti di convegno pubblicato in volume |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| Minimal Absent Words in Rooted and Unrooted Trees.pdf | Versione Editoriale | Administrator Richiedi una copia | ||
| 1907.12034.pdf | Post-print | Open Access Visualizza/Apri |
Copyright © 2022