Titre :

Dualities in Tree Representations

Auteur(s) :

Chikhi, Rayan [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]
Schönhuth, Alexander [Auteur]
Life Sciences [Amsterdam] [MAC4]
Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale [ERABLE]

Mot(s)-clé(s) en anglais :

Succinct Tree Representation
Balanced Parenthesis Representation
Isomorphisms
Data Structures

Discipline(s) HAL :

Informatique [cs]/Bio-informatique [q-bio.QM]
Informatique [cs]/Mathématique discrète [cs.DM]

Résumé en anglais : [en]

A characterization of the tree $T^*$ such that $\mathrm{BP}(T^*)=\overleftrightarrow{\mathrm{DFUDS}(T)}$, the reversal of $\mathrm{DFUDS}(T)$ is given. An immediate consequence is a rigorous characterization of the tree ...
Lire la suite >A characterization of the tree $T^*$ such that $\mathrm{BP}(T^*)=\overleftrightarrow{\mathrm{DFUDS}(T)}$, the reversal of $\mathrm{DFUDS}(T)$ is given. An immediate consequence is a rigorous characterization of the tree $\hat{T}$ such that $\mathrm{BP}(\hat{T})=\mathrm{DFUDS}(T)$. In summary, $\mathrm{BP}$ and $\mathrm{DFUDS}$ are unified within an encompassing framework, which might have the potential to imply future simplifications with regard to queries in $\mathrm{BP}$ and/or $\mathrm{DFUDS}$. Immediate benefits displayed here are to identify so far unnoted commonalities in most recent work on the Range Minimum Query problem, and to provide improvements for the Minimum Length Interval Query problem.Lire moins >

Langue :

Anglais

Commentaire :

CPM 2018, extended version

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL