Annals of Computer Science and Information Systems, Volume 11

DOI: http://dx.doi.org/10.15439/2017F117

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 429–432 (2017)

Full text

Abstract. In the area of applied optimization, heuristics are a popular means to address computational problems of high complexity. Modeling the problem and mapping all variations of its solution into a so-called solution space is an integral part of this process. Representing solutions as graphs is common and, for a special type of graph, Pruefer Code (PC) offers a computationally efficient (algorithms of O(n)-complexity are known) mapping to n-2 dimensional Euclidean space. However, this encoding does not preserve properties such as e.g. locality and therefore PC has been shown to be a bad choice for entire classes of problems. We argue that Pruefer Code does allow the preservation of some properties (e.g. degree of branching and branching vertices) and that these are sufficiently relevant for certain types of problems to motivate encoding them in PC. We present our investigations and provide an example where PC has been shown to be a useful encoding.

References

1. D. Y. Atia. Indoor distributed antenna systems deployment optimization with particle swarm optimization. M.Sc. thesis, Khalifa University of Science, Technology and Research, 2015.
2. D. Y. Atia, D. Ruta, K. Poon, A. Ouali, and A. F. Isakovic. Cost effective, scalable design of indoor distributed antenna systems based on particle swarm optimization and prufer strings. In IEEE 2016 IEEE Congress on Evolutionary Computation, Vancouver, Canada, July 2016.
3. P. Blackburn, M. deRijke, and Y. Venema. Modal Logic. Cambridge University Press, 2001.
4. C. W. Borchardt. Über eine Interpolationsformel für eine Art symmetrischer Funktionen und über deren Anwendung. In Math. Abh. Akad. Wiss. zu Berlin, pages 1–20. Berlin, 1860.
5. A. Cayley. On the theory of the analytical forms called trees. Philosophical Magazine, 13:172–6, 1857.
6. A. Cayley. A theorem on trees, volume 13 of Cambridge Library Collection - Mathematics, pages 26–28. Camb. Univ. Press, July 2009.
7. S.-H. Cha. On complete and size balanced k-ary tree integer sequences. Int. J. of Applied Mathematics and Informatics, 6(2):67–75, 2012.
8. R. Diestel. Graph Theory. Elect. library of mathematics. Springer, 2006.
9. S. K. Ghosh, J. Ghosh, and R. K. Pal. A new algorithm to represent a given k-ary tree into its equivalent binary tree structure. Journal of Physical Sciences, 12:253–264, 2008.
10. J. Gottlieb, B. A. Julstrom, G. R. Raidl, and F. Rothlauf. Prüfer numbers: A poor representation of spanning trees for evolutionary search. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pages 343–350, San Francisco, California, 2001. Morgan Kaufmann Publishers.
11. H. Hildmann, D. Y. Atia, D. Ruta, K. Poon, and A. F. Isakovic. Nature-Inspired Optimization in the Era of IoT: Particle Swarm Optimization (PSO) applied to Indoor Distributed Antenna Systems (I-DAS), chapter tbd, page tbd. Springer, 2018 (forthcoming).
12. B. A. Julstrom. Quick decoding and encoding of Prüfer strings: Exercises in data structures, 2005.
13. P. Micikevičius, S. Caminiti, and N. Deo. Linear-time algorithms for encoding trees as sequences of node labels, 2007.
14. T. Paulden and D. K. Smith. Developing new locality results for the Prüfer Code using a remarkable linear-time decoding algorithm. The Electronic Journal of Combinatorics, 14(1), August 2007.
15. H. Prüfer. Neuer Beweis eines Satzes über Permutationen. Archiv der Mathematik und Physik, 27:742–744, 1918.
16. P. V. Ramanan and C.L. Liu. Permutation representation of k-ary trees. Theoretical Computer Science, 38:83 – 98, 1985.