Approximation of trees by self-nested trees

Romain Azaïs (1, 2) , Jean-Baptiste Durand (3) , Christophe Godin (4)

1 BIGS - Biology, genetics and statistics
2 IECL - Institut Élie Cartan de Lorraine
3 MISTIS - Modelling and Inference of Complex and Structured Stochastic Systems
4 VIRTUAL PLANTS - Modeling plant morphogenesis at different scales, from genes to phenotype

The class of self-nested trees presents remarkable compression properties because of the systematic repetition of subtrees in their structure. In this paper, we provide a better combinatorial characterization of this specific family of trees. We show that self-nested trees may be considered as an approximation class of unordered trees. We compare our approximation algorithms with a competitive approach of the literature on a simulated dataset.

Mots clés: Unordered trees; Self-nested trees; Directed acyclic graphs; Approximation class

Domaines: Algorithme et structure de données [cs.DS]

Romain Azaïs, Jean-Baptiste Durand, Christophe Godin. Approximation of trees by self-nested trees. 2016. ⟨hal-01294013v2⟩