zbMATH — the first resource for mathematics

Unified parallel encoding and decoding algorithms for Dandelion-like codes. (English) Zbl 1233.68222
Summary: The Dandelion-like codes are eight bijections between labeled trees and strings of node labels. The literature contains optimal sequential algorithms for these bijections, but no parallel algorithms have been reported. In this paper the first parallel encoding and decoding algorithms for Dandelion-like codes are presented. Namely, a unique encoding algorithm and a unique decoding algorithm, which when properly parameterized, can be used for all Dandelion-like codes, are designed. These algorithms are optimal in the sequential setting. The encoding algorithm implementation on an EREW PRAM is optimal, while the efficient implementation of the decoding algorithm requires concurrent reading.

68W10 Parallel algorithms in computer science
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
94B60 Other types of codes
Full Text: DOI
[1] Bau, Y. T.; Ho, C. K.; Ewe, H. T.: Ant colony optimization approaches to the degree-constrained minimum spanning tree problem, Journal of information science and engineering 24, 1081-1094 (2008)
[2] V. Boppana, I. Hartanto, W.K. Fuchs, Full fault dictionary storage based on labeled tree encoding, in: Proceedings of the 14th IEEE VLSI Test Symposium, VTS’96, 1996, pp. 174–179.
[3] S. Caminiti, On Coding Labeled Trees, Ph.D. Thesis, Sapienza University of Rome, 2007. · Zbl 1188.68116
[4] Caminiti, S.; Deo, N.; Micikevičius, P.: Linear-time algorithms for encoding trees as sequences of node labels, Congressus numerantium 183, 65-75 (2006) · Zbl 1111.68036
[5] Caminiti, S.; Finocchi, I.; Petreschi, R.: On coding labeled trees, Theoretical computer science 382, No. 2, 97-108 (2007) · Zbl 1188.68116 · doi:10.1016/j.tcs.2007.03.009
[6] S. Caminiti, R. Petreschi, Optimal algorithms for Chen code, Technical Report TR-02-2009, Department of Computer Science, Sapienza University of Rome, March 2009. · Zbl 1274.68679
[7] S. Caminiti, R. Petreschi, String coding of trees with locality and heritability, in: Proceedings of the 11th International Conference on Computing and Combinatorics, COCOON’05, in: LNCS, vol. 3595, 2005, pp. 251–262. · Zbl 1128.68397
[8] S. Caminiti, R. Petreschi, Parallel algorithms for Blob code, in: Proceedings of the 3rd Workshop on Algorithms and Computation, WALCOM’2010, in: LNCS, vol. 5942, 2010, pp. 167–178. · Zbl 1274.68679
[9] S. Caminiti, R. Petreschi, Parallel algorithms for Dandelion-Like codes, in: Proceedings of the 9th International Conference on Computational Science, ICCS’09, in: LNCS, vol. 5544, 2009, pp. 611–620. · Zbl 1233.68222
[10] Cayley, A.: A theorem on trees, Quarterly journal of mathematics 23, 376-378 (1889) · JFM 21.0687.01
[11] W.Y.C. Chen, A general bijective algorithm for trees, in: Proceeding of the National Academy of Science, vol. 87, 1990, pp. 9635–9639. · Zbl 0707.05019 · doi:10.1073/pnas.87.24.9635
[12] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.: Introduction to algorithms, (2001) · Zbl 1047.68161
[13] Deo, N.; Kumar, N.; Kumar, V.: Parallel generation of random trees and connected graphs, Congressus numerantium 130, 7-18 (1998) · Zbl 0953.68118
[14] Deo, N.; Micikevičius, P.: A new encoding for labeled trees employing a stack and a queue, Bulletin of the institute of combinatorics and its applications (ICA) 34, 77-85 (2002) · Zbl 0996.05035
[15] Deo, N.; Micikevičius, P.: Prüfer-like codes for labeled trees, Congressus numerantium 151, 65-73 (2001) · Zbl 0993.68033
[16] N. Deo, P. Micikevičius, Parallel algorithms for computing Prüfer-Like codes of labeled trees, Technical Report CS-TR-01-06, Department of Computer Science, University of Central Florida, Orlando, 2001.
[17] Devroye, L.: Non-uniform random variate generation, (1986) · Zbl 0593.65005
[18] W. Edelson, M.L. Gargano, Feasible encodings For GA solutions of constrained minimal spanning tree problems, in: Proceedings of the 5th Genetic and Evolutionary Computation Conference, GECCO’00, Las Vegas, NV, USA, 2000, pp. 82–89. · Zbl 0972.68130
[19] Eğecioğlu, Ö.; Remmel, J. B.: Bijections for Cayley trees, spanning trees, and their q-analogues, Journal of combinatorial theory 42A, No. 1, 15-30 (1986) · Zbl 0595.05025 · doi:10.1016/0097-3165(86)90004-X
[20] V.K. Garg, A. Agarwal, Distributed maintenance of a spanning tree using labeled tree encoding, in: Proceedings of 11th International Euro-Par Conference, Euro-Par’05, in: LNCS, vol. 3648, 2005, pp. 606–616.
[21] R. Greenlaw, M.M. Halldórsson, R. Petreschi, On computing Prüfer codes and their corresponding trees optimally in parallel, in: Proceedings of Journées de l’Informatique Messine, JIM’00, Metz, France, 2000. · Zbl 0961.68153
[22] Greenlaw, R.; Petreschi, R.: Computing Prüfer codes efficiently in parallel, Discrete applied mathematics 102, No. 3, 205-222 (2000) · Zbl 0961.68153 · doi:10.1016/S0166-218X(99)00221-8
[23] Jájá, J.: An introduction to parallel algorithms, (1992) · Zbl 0781.68009
[24] P. Klingsberg, Doctoral Dissertation, Ph.D. Thesis, University of Washington, Seattle, Washington, 1977.
[25] Kreweras, G.; Moszkowski, P.: Tree codes that preserve increases and degree sequences, Journal of discrete mathematics 87, No. 3, 291-296 (1991) · Zbl 0825.94236 · doi:10.1016/0012-365X(91)90138-R
[26] P. Micikevičius, Parallel graph algorithms for molecular conformation and tree codes, Ph.D. Thesis, University of Central Florida, 2002.
[27] Moon, J. W.: Counting labeled trees, (1970) · Zbl 0214.23204
[28] E.H. Neville, The codifying of tree-structure, in: Proceedings of Cambridge Philosophical Society, vol. 49, 1953, pp. 381–385. · Zbl 0050.17904
[29] T. Paulden, D.K. Smith, Recent advances in the study of the Dandelion Code, happy code, and blob code spanning tree representations, in: Proceedings of the IEEE Congress on Evolutionary Computation, CEC’06, 2006, pp. 2111–2118.
[30] Y.A. Phoulady, M. Behzadi, H. Taheri, Sharing a labeled tree, in: Proceedings of the 4th Benelux Workshop on Information and System Security, WISSec’09, 2009.
[31] S. Picciotto, How to Encode a Tree, Ph.D. Thesis, University of California, San Diego, 1999.
[32] Prüfer, H.: Neuer beweis eines satzes über permutationen, Archiv der Mathematik und physik 27, 142-144 (1918) · JFM 46.0106.04
[33] P. Rao, B. Moon, Prix: indexing and querying xml using prufer sequences, in: Proceedings of the International Conference on Data Engineering, ICDE’04, 2004, pp. 288–300.
[34] Reeves, C. R.; Rowe, J. E.: Genetic algorithms: A guide to GA theory, (2003) · Zbl 1029.90081
[35] Reif, J. H.: Synthesis of parallel algorithms, (1993) · Zbl 0772.94019
[36] C. Vanniarajan, K. Krithivasan, Network (tree) topology inference based on Prüfer sequence, in: Proceedings of the 16th National Conference on Communications, NCC’10, 2010.
[37] Vishkin, U.; Caragea, G. C.; Lee, B.: Models for advancing PRAM and other algorithms into parallel programs for a PRAM-on-chip platform, Handbook of parallel computing: models, algorithms and applications (2008)
[38] Wang, Yue-Li; Chen, Hon-Chan; Liu, Wei-Kai: A parallel algorithm for constructing a labeled tree, IEEE transactions on parallel and distributed systems 8, 1236-1240 (1997)
[39] X. Wen, U. Vishkin, PRAM-on-chip: first commitment to silicon, in: Proceedings of the 19th ACM Symposium on Parallel Algorithms and Architectures, SPAA’07, 2007, pp. 301–302.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.