Graph Colouring and Branch and Bound Approaches for Permutation Code Algorithms

Roberto Montemanni, János Barta, Derek H. Smith

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review


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.

Original languageEnglish
Title of host publicationNew Advances in Information Systems and Technologies
EditorsÁlvaro Rocha, Ana Maria Correia, Hojjat Adeli, Luis Paulo Reis, Marcelo Mendonça Teixeira
ISBN (Electronic)978-3-319-31232-3
ISBN (Print)978-3-319-31231-6
Publication statusPublished - 2 Mar 2016

Publication series

NameAdvances in Intelligent Systems and Computing
ISSN (Print)2194-5357
ISSN (Electronic)2194-5365


  • Permutation codes
  • Maximum clique algorithms
  • Branch and bound
  • Colouring bound


Dive into the research topics of 'Graph Colouring and Branch and Bound Approaches for Permutation Code Algorithms'. Together they form a unique fingerprint.

Cite this