Czasopismo | PRZEGLĄD ELEKTROTECHNICZNY | Rocznik 2012 - zeszyt 7b

Efficient Tree Coding Algorithms

nr katalogowy: 69358

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. Streszczenie. W artykule rozważano problem kodu Neville drugiego rzędu stosowanego do etykietowania elementów struktury typu drzewo. (Skuteczny algorytm kodowania drzewa) Keywords: Labeled trees, Neville codes, depth first search, optimal algorithms. Słowa kluczowe: kodowane drzewo, kod Neville Introduction Labeled trees are of interest in practical and theoretical areas of computer science. For example, Ethernet has a unique path between terminal devices, thus being a tree: labeling the tree nodes is necessary to uniquely identify each device in the network. An interesting alternative to the usual representations of tree data structures in computer memories is based on coding labeled trees by means of strings of node labels. This representation was first used in the proof of Cayley’s theorem [3] to show a one-to-one correspondence between free labeled trees on n nodes and strings of length n - 2. In addition to this purely mathematical use, string-based coding of trees have many practical applications. For instance, they make it possible to generate random uniformly distributed trees and random connected graphs: the generation of a random string followed by the use of a fast decoding algorithm is typically more efficient than random tree generation by the addition of edges, since in the latter case o[...]

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


e-Publikacja (format pdf) - nr 69358 "Efficient Tree Coding Alg..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


PRZEGLĄD ELEKTROTECHNICZNY - e-zeszyt (pdf) 2012-7b licencja: Osobista Produkt cyfrowy	55.00 zł

Prenumerata

PRZEGLĄD ELEKTROTECHNICZNY - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

762.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	1002.00 zł brutto 927.78 zł netto 74.22 zł VAT (stawka VAT 8%)

1002.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna	960.00 zł brutto 888.89 zł netto 71.11 zł VAT (stawka VAT 8%)
PRZEGLĄD ELEKTROTECHNICZNY - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

1002.00 zł

Zeszyt

2012-7b

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma