Minimal Absent Words in Rooted and Unrooted Trees

Gabriele Fici, Paweł Gawrychowski

Risultato della ricerca: Conference contribution

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.
Lingua originaleEnglish
Titolo della pubblicazione ospiteLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pagine152-161
Numero di pagine10
Stato di pubblicazionePublished - 2019

Serie di pubblicazioni

NomeLECTURE NOTES IN ARTIFICIAL INTELLIGENCE

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • ???subjectarea.asjc.1700.1700???

Fingerprint Entra nei temi di ricerca di 'Minimal Absent Words in Rooted and Unrooted Trees'. Insieme formano una fingerprint unica.

Cita questo