Efficient Tree Coding Algorithms

• Autorzy: Wang X. , Tian J.

Warianty tytułu

PL

Skuteczny algorytm kodowania drzewa

• Języki publikacji: EN

Abstrakty

EN

This paper studies the algorithms for coding and decoding second Neville’s codes of a labeled tree. The algorithms for coding and decoding second Neville’s codes of a labeled tree in the literatures require O(n log n) time usually. As stated in [1][2], no linear time algorithms for the second Neville’s codes. In this paper we consider the second Neville’s code problem in a different angle and a more direct manner. We start from a naïve algorithm, then improved it gradually and finally we obtain a very practical linear time algorithm. The techniques we used in this paper are interesting themselves.

PL

W artykule rozważano problem kodu Neville drugiego rzędu stosowanego do etykietowania elementów struktury typu drzewo.

Słowa kluczowe

EN

Labeled trees; Neville codes; depth-first search; optimal algorithms

PL

drzewo kodowane; kod Neville

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2012
• Tom: R. 88, nr 7b
• Strony: 350--352
• Opis fizyczny: Bibliogr. 10 poz..

Twórcy

autor

Wang X.

• Quanzhou Normal University, Quanzhou 362000, P.R.China

autor

Tian J.

• Fujian Medical University, PR China

Bibliografia

• [1] S. Caminiti, I. Finocchi, and R. Petreschi. A Unified Approach to Coding Labeled Trees. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN '04), LNCS 2976, 339-348, 2004.
• [2] S. Caminiti, I. Finocchi, and R. Petreschi. On Coding Labeled Trees. To appear on Theoretical Computer Science, 2006.
• [3] A.Cayley, A theorem on trees. Quarterly Journal of Mathematics, 23, 376–378, 1889.
• [4] H.C. Chen and Y.L.Wang, An efficient algorithm for generating Neville codes from labeled trees. Theory of Computing Systems, 33, 97–105, 2000.
• [5] N. Deo and P.Micikevicius, Parallel algorithms for computing Neville-like codes of labeled trees. Computer Science Technical Report CS-TR-01-06, 2001.
• [6]W. Edelson and M.L.Gargano, Feasible encodings for GA solutions of constrained minimal spanning tree problems. Proceedings of the Genetic and Evolutionary Computation Conference, 754-755, 2000.
• [7] A. Kelmans, I.Pak and A.Postnikov, Tree and forest volumes of graphs. DIMACS Technical Report 2000-03, 2000.
• [8]V.Kumar, N.Deo and N.Kumar, Parallel generation of random trees and connected graphs. Congressus Numerantium, 130, 7–18, 1998.
• [9]E. H. Neville. The codifying of tree-structure. Proceedings of Cambridge Philosophical Society, vol. 49, 381-385, 1953.
• [10]G. Zhou and M.Gen, A note on genetic algorithms for degreeconstrained spanning tree problems. Networks, 30, 91–95, 1997.