<abstract xmlns="http://www.w3.org/1999/xhtml">In the paper we give some theoretical and computational results on the third strong power of cycle-powers, for example, we have found the independence numbers <italic>α</italic>((<italic>C</italic>102)√3) = 30 and <italic>α</italic>((<italic>C</italic>144)√3) = 14. A number of optimizations have been introduced to improve the running time of our exhaustive algorithm used to establish the independence number of the third strong power of cycle-powers. Moreover, our results establish new exact values and/or lower bounds on the Shannon capacity of noisy channels.</abstract>

In the paper we give some theoretical and computational results on the third strong power of cycle-powers, for example, we have found the independence numbers α((C102)√3) = 30 and α((C144)√3) = 14. A number of optimizations have been introduced to improve the running time of our exhaustive algorithm used to establish the independence number of the third strong power of cycle-powers. Moreover, our results establish new exact values and/or lower bounds on the Shannon capacity of noisy channels.

On The Independence Number Of Some Strong Products Of Cycle-Powers

Gdansk University of Technology, Faculty of Electronics, Telecommunications and Informatics, Department of Algorithms and System Modelling, Gabriela Narutowicza 11/12, 80-233 Gdansk, Poland

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"On The Independence Number Of Some Strong Products Of Cycle-Powers"}

In the paper we give some theoretical and computational results on the third strong power of cycle-powers, for example, we have found the independence numbers...

On The Independence Number Of Some Strong Products Of Cycle-Powers

Publié en ligne: 16 mai 2015

Pages: 133 - 141

Reçu: 06 oct. 2014

Accepté: 11 févr. 2015

DOI: https://doi.org/10.1515/fcds-2015-0009

Mots clés
strong product, exhaustive search algorithm, independence number, Shannon capacity

© Marcin Jurkiewicz et al.

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

On The Independence Number Of Some Strong Products Of Cycle-Powers

Publié en ligne: 16 mai 2015

Pages: 133 - 141

Reçu: 06 oct. 2014

Accepté: 11 févr. 2015

DOI: https://doi.org/10.1515/fcds-2015-0009

Mots clésstrong product, exhaustive search algorithm, independence number, Shannon capacity

© Marcin Jurkiewicz et al.

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
strong product, exhaustive search algorithm, independence number, Shannon capacity