Abstract
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 Prüfer 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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cayley, A.: A theorem on trees. Quarterly Journal of Mathematics 23, 376–378 (1889)
Caminiti, S., Finocchi, I., Petreschi, R.: A unified approach to coding labeled trees. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 339–348. Springer, Heidelberg (2004)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. McGraw-Hill, New York (2001)
Deo, N., Micikevicius, P.: Parallel algorithms for computing Prüfer-like codes of labeled trees. Computer Science Technical Report, CS-TR-01-06 (2001)
Edelson, W., Gargano, M.L.: Feasible encodings for GA solutions of constrained minimal spanning tree problems. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2000), p. 754. Morgan Kaufmann Publishers, San Francisco (2000)
Gottlieb, J., Raidl, G., Julstrom, B.A., Rothlauf, F.: Prüfer Numbers: A Poor Representation of Spanning Trees for Evolutionary Search. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pp. 343–350 (2001)
Julstrom, B.A.: The Blob Code: A Better String Coding of Spanning Trees for Evolutionary Search. In: 2001 Genetic and Evolutionary Computation Conference Workshop Program, pp. 256–261 (2001)
Kelmans, A., Pak, I., Postnikov, A.: Tree and forest volumes of graphs. DIMACS Technical Report 2000-03 (2000)
Kumar, V., Deo, N., Kumar, N.: Parallel generation of random trees and connected graphs. Congressus Numerantium 130, 7–18 (1998)
Picciotto, S.: How to encode a tree. Ph.D. Thesis, University of California, San Diego (1999)
Prüfer, H.: Neuer Beweis eines Satzes über Permutationen. Archiv für Mathematik und Physik 27, 142–144 (1918)
Zhou, G., Gen, M.: A note on genetic algorithms for degree-constrained spanning tree problems. Networks 30(2), 91–95 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Caminiti, S., Petreschi, R. (2005). String Coding of Trees with Locality and Heritability. In: Wang, L. (eds) Computing and Combinatorics. COCOON 2005. Lecture Notes in Computer Science, vol 3595. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11533719_27
Download citation
DOI: https://doi.org/10.1007/11533719_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28061-3
Online ISBN: 978-3-540-31806-4
eBook Packages: Computer ScienceComputer Science (R0)