A bijective code is a method for associating labeled n-trees to (n-2)-strings of node labels in such a way that different trees yield different strings and vice versa. For all known bijective codes, optimal sequential encoding and decoding algorithms are presented in literature, while parallel algorithms are investigated only for some of these codes. In this paper we focus our attention on the Blob code: a code particularly considered in the field of Genetic Algorithms. To the best of our knowledge, here we present the first parallel encoding and decoding algorithms for this code. The encoding algorithm implementation is optimal on an EREW PRAM, while the decoding algorithm requires O(log n) time and O(n) processors on CREW PRAM. © 2010 Springer.
Parallel Algorithms for Encoding and Decoding Blob Code / Saverio, Caminiti; Petreschi, Rossella. - STAMPA. - 5942:(2010), pp. 167-178. (Intervento presentato al convegno 4th International Workshop on Algorithms and Computation (WALCOM 2010) tenutosi a Dhaka, BANGLADESH nel FEB 10-12, 2010) [10.1007/978-3-642-11440-3_16].
Parallel Algorithms for Encoding and Decoding Blob Code
PETRESCHI, Rossella
2010
Abstract
A bijective code is a method for associating labeled n-trees to (n-2)-strings of node labels in such a way that different trees yield different strings and vice versa. For all known bijective codes, optimal sequential encoding and decoding algorithms are presented in literature, while parallel algorithms are investigated only for some of these codes. In this paper we focus our attention on the Blob code: a code particularly considered in the field of Genetic Algorithms. To the best of our knowledge, here we present the first parallel encoding and decoding algorithms for this code. The encoding algorithm implementation is optimal on an EREW PRAM, while the decoding algorithm requires O(log n) time and O(n) processors on CREW PRAM. © 2010 Springer.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
