Abstract
A considerable amount of research has been devoted to permutation codes in recent years. This has been motivated by some real-world applications. Permutation codes are important because of their robustness against transmission errors and noise. This study addresses the problem of the construction of the largest possible permutation codes with given parameters, namely a specified length and minimum Hamming distance. The problem is modelled in terms of maximum cliques and it is shown how a well-known upper bound based on colouring can be successfully embedded inside a branch and bound method. Experimental results are presented to evaluate the effectiveness of the new idea.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Operations Research Letters, 9 375–382 (1990)
Montemanni, R.: Combinatorial optimization algorithms for the design of codes: a survey. Journal of Applied Operations Research 7(1):36–41 (2015)
Deza, M., Vanstone, S.A.: Bounds for permutation arrays. Journal of Statistical Planning and Inference 2 197–209 (1978)
Blake, I.F.: Permutation codes for discrete channels. IEEE Transactions on Information Theory 20(1) 138–140 (1974)
Bogaerts, M.: New upper bounds for the size of permutation codes via linear programming. The Electronic Journal of Combinatorics 17(#R135) (2010)
Chu, W., Colbourn, C.J., Dukes, P.: Constructions for permutation codes in powerline communications. Designs, Codes and Cryptography 32, 51–64 (2004)
Dukes, P., Sawchuck, N.: Bounds on permutation codes of distance four. Journal of Algebraic Combinatorics 31 143–158 (2010)
Frankl, P., Deza, M.: On maximal numbers of permutations with given maximal or minimal distance. Journal of Combinatorial Theory Series A 22, 352–260 (1977)
Janiszczak, I., Staszewski, R.: An improved bound for permutation arrays of length 10, http://www.iem.uni-due.de/preprints/IJRS.pdf (downloaded 9th November 2015)
Tarnanen, H.: Upper bounds on permutation codes via linear programming. European Journal of Combinatorics 20 101–114 (1999)
Colbourn, C.J., Kløve, T., Ling, A.C.H.: Permutation arrays for powerline communication and mutually orthogonal latin squares. IEEE Transactions on Information Theory 50, 1289–1291 (2004)
Gao, F., Yang, Y., Ge, G.: An improvement on the Gilbert-Varshamov bound for permutation codes. IEEE Transactions on Information Theory 59(5), 3059–3063 (2013)
Han Vinck, A.J.: Coded modulation for power line communications. A.E.Ü. International Journal Electronics and Communications 54(1), 45–49 (2000)
Ferreira, H.C., Han Vinck, A.J.: Inference cancellation with permutation trellis arrays. Proceedings of the IEEE Vehicular Technology Conference, 2401–2407 (2000)
Huczynska, S.: Powerline communications and the 36 officers problem. Philosophical Transactions of the Royal Socicety A. 364, 3199–3214 (2006)
Pavlidou, N., Han Vinck, A.J., Yazdani, J., Honary, B.: Power line communications: state of the art and future trends. IEEE Communications Magazine 41(4), 34–40 (2003)
de la Torre, D.R., Colbourn, C.J., Ling, A.C.H.: An application of permutation arrays to block ciphers. Proceedings of the 31st Southeastern International Conference on Combinatorics, Graph Theory and Computing 145, 5–7 (2000)
Jiang, A., Mateescu, R., Schwartz, M., Bruck, J.: Rank modulation for flash memories. Proceedings of the IEEE International Symposium on Information Theory, 1731–1735 (2008)
Jiang, A., Schwartz, M., Bruck, J.: Error-correcting codes for rank modulation. Proceedings of the IEEE International Symposium on Information Theory, 1736–1740 (2008)
Smith, D.H., Montemanni, R.: A new table of permutation codes. Designs, Codes and Cryptography 63(2), 241–253 (2012)
Janiszczak, I., Lempken, W., Östergård, P.R.J., Staszewski, R.: Permutation codes invariant under isometries. Designs, Codes and Cryptography 75, 497–507 (2015)
Montemanni, R., Barta, J., Smith, D.H.: Permutation codes: a new upper bound for M(7,5). Proceedings of the International Conference on Pure Mathematics, Applied Mathematics, Computional Methods, 86–90 (2014)
Montemanni, R., Barta, J., Smith, D.H.: Permutation Codes: a branch and bound approach. Proceedings of the International Conference on Informatics and Advanced Computing, 1–3 (2014)
Barta, J., Montemanni, R., Smith, D.H.: A branch and bound approach to permutation codes. Proceedings of the IEEE 2nd International Conference of Information and Communication Technology, 187–192 (2014)
Barta, J., Montemanni, R., Smith, D.H.: Permutation Codes via Fragmentation of Group Orbits. Proceedings of the IEEE 3rd International Conference of Information and Communication Technology, 39–44 (2015)
Montemanni, R., Barta, J., Smith, D.H.: The design of permutation codes via a specialized maximum clique algorithm. Proceedings of the IEEE 2rd International Conference on Mathematics and Computers in Science and Industry (to appear)
Smith, D.H., Montemanni, R.: Permutation codes with specified packing radius. Designs, Codes and Cryptography 69, 95–106 (2013)
Östergård, P.R.J.: A fast algorithm for the maximum clique problem. Discrete Applied Mathematics 120, 197–207 (2002)
Mehrotra, A., Trick, M.A.: A column generation approach for graph coloring. INFORMS Journal on Computing 8, 344–354 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Montemanni, R., Barta, J., Smith, D.H. (2016). Graph Colouring and Branch and Bound Approaches for Permutation Code Algorithms. In: Rocha, Á., Correia, A., Adeli, H., Reis, L., Mendonça Teixeira, M. (eds) New Advances in Information Systems and Technologies. Advances in Intelligent Systems and Computing, vol 444. Springer, Cham. https://doi.org/10.1007/978-3-319-31232-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-31232-3_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-31231-6
Online ISBN: 978-3-319-31232-3
eBook Packages: EngineeringEngineering (R0)