Edit Distance between Unlabeled Ordered Trees

Simple item page
dc.creatorMicheli, Anne
dc.creatorRossin, Dominique
dc.date2005-06-27
dc.date.accessioned2026-07-07T05:21:10Z
dc.date.available2026-07-07T05:21:10Z
dc.descriptionThere exists a bijection between one stack sortable permutations --permutations which avoid the pattern 231-- and planar trees. We define an edit distance between permutations which is coherent with the standard edit distance between trees. This one-to-one correspondence yields a polynomial algorithm for the subpermutation problem for $(231)$ avoiding permutations. Moreover, we obtain the generating function of the edit distance between ordered trees and some special ones. For the general case we show that the mean edit distance between a planar tree and all other planar trees is at least $n/ln(n)$. Some results can be extended to labeled trees considering colored Dyck paths or equivalently colored one stack sortable permutations.
dc.descriptionAlgorithmique et Combinatoire
dc.identifierhttps://arxiv.org/abs/math/0506538
dc.identifierhttp://arxiv.org/abs/math/0506538
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/75593
dc.subjectCombinatorics
dc.subjectDiscrete Mathematics
dc.subject05C12,05C05,05A05,05A15
dc.titleEdit Distance between Unlabeled Ordered Trees
dc.typetext

Files

Collections

arXiv