String Coding of Trees with Locality and Heritability
(0) We consider the problem of coding labelled trees by means of strings of vertex labels and we present a general scheme to define bijective codes based on the transformation of a tree into a functional digraph. Looking at the fields in which codes for labelled trees are utilized, we see that the properties of locality and heritability are required and that codes like the well known Prufer code do not satisfy these properties. We present a general scheme for generating codes based on the construction of functional digraphs. We prove that using this scheme, locality and heritability are satisfied as a direct function of the similarity between the topology of the functional digraph and that of the original tree. Moreover, we also show that the efficiency of our method depends on the transformation of the tree into a functional digraph. Finally we show how it is possible to fit three known codes into our scheme, obtaining maximum efficiency and high locality and heritability.
Saverio Caminiti Rossella Petreschi
Dipartimento di Informatics, Universita degli Studi di Roma La Sapienza Via Salaria 113, 00198 Roma, Italy
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
251-262
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）