A parallel dynamic programming algorithm for unranking t-ary trees / Zbigniew Kokosiński // W: Parallel Processing and Applied Mathematics : 5th International Conference, PPAM 2003 Częstochowa, Poland, ... więcej

A parallel dynamic programming algorithm for unranking t-ary trees / Zbigniew Kokosiński // W: Parallel Processing and Applied Mathematics : 5th International Conference, PPAM 2003 Częstochowa, Poland, September 7-10, 2003 : revised papers [Dokument elektroniczny] / eds. Roman Wyrzykowski [et al.]. – Berlin ; Heidelberg : Springer, 2004. – (Lecture Notes in Computer Science, ISSN 1611-3349 ; 3019). – S. 255-260 : tab. – Tryb dostępu: https://link.springer.com/chapter/10.1007/978-3-540-24669-5_33. – Bibliogr. 20 poz., Abstr. – doi: 10.1007/978-3-540-24669-5_33. – ISBN 978-3-540-24669-5 (online). – ISBN 978-3-540-21946-0 (print). – ISBN 3-540-21946-3

In this paper an O(n) parallel algorithm is presented for fast unranking t–ary trees with n internal nodes in Zaks’ representation. A sequential O(nt) algorithm is derived on the basis of dynamic programming ... więcej

In this paper an O(n) parallel algorithm is presented for fast unranking t–ary trees with n internal nodes in Zaks’ representation. A sequential O(nt) algorithm is derived on the basis of dynamic programming paradigm. In the parallel version of the algorithm processing is performed in a dedicated parallel architecture containing certain systolic and associative features. At first a coefficient table is created by systolic computations. Then, n subsequent elements of a tree codeword is computed in O(1) time through associative search operations.