We consider the problem of coding labeled trees by means of strings of node labels. Different codes have been introduced in the literature by Prufer, Neville, and Deo and Micikevicius. For all of them, we show that both coding and decoding can be reduced to integer (radix) sorting, closing several open problems within a unified framework that can be applied both in a sequential and in a parallel setting. Our sequential coding and decoding schemes require optimal O(n) time when applied to n-node trees, yielding the first linear time decoding algorithm for a code presented by Neville. These schemes can be parallelized on the EREW PRAM model. so as to work in O(log n) time with cost O(n), O(n root log n), or O(n log n), depending on the code and on the operation: in all cases, they either match or improve the performances of the best ad hoc approaches known so far. (c) 2007 Elsevier B.V. All rights reserved.
On coding labeled trees / Caminiti, Saverio; Finocchi, Irene; Petreschi, Rossella. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 382:2(2007), pp. 97-108. (Intervento presentato al convegno 6th Latin American Symposium on Theoretical Informatics (LATIN 2004) tenutosi a Buenos Aires, ARGENTINA nel APR 05-08, 2004) [10.1016/j.tcs.2007.03.009].
On coding labeled trees
CAMINITI, SAVERIO;FINOCCHI, Irene;PETRESCHI, Rossella
2007
Abstract
We consider the problem of coding labeled trees by means of strings of node labels. Different codes have been introduced in the literature by Prufer, Neville, and Deo and Micikevicius. For all of them, we show that both coding and decoding can be reduced to integer (radix) sorting, closing several open problems within a unified framework that can be applied both in a sequential and in a parallel setting. Our sequential coding and decoding schemes require optimal O(n) time when applied to n-node trees, yielding the first linear time decoding algorithm for a code presented by Neville. These schemes can be parallelized on the EREW PRAM model. so as to work in O(log n) time with cost O(n), O(n root log n), or O(n log n), depending on the code and on the operation: in all cases, they either match or improve the performances of the best ad hoc approaches known so far. (c) 2007 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
