Approximation of trees by self-nested trees

DOI10.1137/1.9781611975499.4MaRDI QIDQ5232750zbMATH OpenOpenAlexFDO

Authors Romain Azaïs, Jean-Baptiste Durand, Christophe Godin

Publication date 13 September 2019

Published in 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.10860

Mathematics Subject Classification ID

Data structures (68P05) Approximation algorithms (68W25)

Abstract: 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. In particular, we show from both theoretical and practical viewpoints that complex queries can be quickly answered in self-nested trees compared to general trees. We also present an approximation algorithm of a tree by a self-nested one that can be used in fast prediction of edit distance between two trees.

Recommendations

• Tree compression with top trees
• Tree compression with top trees
• Algorithmic height compression of unordered trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems

Cited in

(2)

• Characterization of random walks on space of unordered trees using efficient metric simulation
• Enumeration of irredundant forests

This page was built for publication: Approximation of trees by self-nested trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232750)