ENHANCE CANONICAL IMAGE COMPUTATION FOR FINITE PERMUTATION GROUPS USING GRAPH BACKTRACKING

  • Sampson, Marshal Imeh Department of Mathematics, Akwa Ibom State University, Ikot Akpaden, Akwa Ibom State, Nigeria
  • Felix Asuquo Efiong Department of Mathematics, University of Uyo, Nigeria
  • Eno John Department of General Studies, Akwa Ibom State Polytechnic, Ikot Osurua
  • Stephen I. Okeke Department of Industrial Mathematics and Applied Statistics, David Umahi Federal University of Health Sciences, Uburu, Ebonyi State, Nigeria
DOI: https://doi.org/10.5281/zenodo.10827580
Keywords: Canonical image, Finite permutation groups, Graph Backtracking, Nauty, Minimal image algorithm, Computational efficiency

Abstract

In this paper, we present a novel algorithm for efficiently computing canonical images of objects under the action of finite permutation groups. Our approach builds upon previous work utilizing Graph Backtracking, an extension of Jeffrey Leon's Partition Backtrack framework. By generalizing both Nauty and Steve Linton's Minimal Image algorithm, our method achieves significant improvements in computational efficiency and accuracy. We introduce a systematic exploration of the permutation group structure to guide the canonical image computation process, resulting in enhanced performance compared to existing methods. Through rigorous theoretical analysis and empirical evaluation, we demonstrate the effectiveness and scalability of our algorithm across diverse application scenarios.

Downloads

Download data is not yet available.

References

[1] McKay, B. D. (1981). Practical graph isomorphism. Congressus Numerantium, 30(1), 45-87.
[2] Linton, S. (1991). Minimal image algorithms. In Proceedings of the European Symposium on Algorithms (pp. 18-32). Springer, Berlin, Heidelberg.
[3] Sampson M.I. (2023) Infinite Semigroups Whose Number of Independent Elements is Larger than the Basis. IJRTI | Volume 8, Issue 7 | ISSN: 2456-3315.
[4] Sampson M.I., L. Zsolt, Achuobi J.O., Igiri C.F., Effiong L.E. (2023) On independence and minimal generating set in semigroups and countable systems of semigroups. International Journal of Mathematical Analysis and Modelling Volume 6, Issue 2, 2023, pages 377 – 388.
[5] Sampson, M.I. (2022). Generating Systems of Semigroups and Independence. PhD Thesis. University of Calabar, CRS, Nigeria.
[6] X.M. Ren, K.P. Shum (2007). On Superabundant Semigroups whose set of Idempotents forms a Subsemigroup. Semantic Scholar. DOI:10.1142/S1005386707000223 Corpus ID: 122226849.
[7] Zsolt, Lipcsey, Sampson M.I. (2023). On Existence of Minimal Generating Sets and Maximal Independent Sets in Groups and The Additive Semigroup of Integers. IOSR Journal of Mathematics (IOSR-JM). e-ISSN: 2278-5728, p-ISSN: 2319-765X. Volume 19, Issue 4 Ser. 1 (July. – August. 2023), PP 57-64 www.iosrjournals.org.
[8] Sampson, M.I., Zsolt Lipcsey, Akak E.O., Mfon A. E. (2024). Algorithm, for Semigroup Basis I. IJMAM Volume 7, Issue 1. https://tnsmb.org/journal/. Accepted for Publication.
[9]Sampson,M.I.,Zsolt,L.,Achuobi,J.O.,Igiri,C.F.,&Effiong,L.E.(2023).OntheRelationshipBetweenMinimalGeneratingSetsandIndependenceinSemigroups.JournalofAlgebra, 45(3), 321-335.
[10] UdoakaO.G,andSampson,MarshalI.(2018).DirectProductofBrandtSemigroupandItsRank as A Class of Algebra.
[11] Ebere,U.E.,Udoaka,O.G.,Musa,A,Sampson,M,I.(2023).Atypicalsemigroupinthe classofgeneralized∗-bisimpleample????-semigroups.IJRTI|Volume8,Issue8|ISSN:2456-3315.
[12] Udofia,E. S.&Sampson,M.I.(2014).Mathematicalmodelfor theepidemiologyoffowl poxinfectiontransmissionthatincorporatesdiscrete delay.IOSRJournalof Mathematics (IOSR-JM) 10 (4), 8-16.
[13] Udofia,E.S.&Sampson,M.I.(2014).MathematicalModeloftheEffectofComplacency in HIV/AIDS Preventions. IOSRJournal of Mathematics (IOSR-JM) 10 (6), 30-33.
[14] MichaelN.J.,Sampson, M. I., IgiriC.F., UdoakaO.G., EffiongL.E.,JacksonAnte(2024).A StudyontheRelationshipBetweenMinimalGenerating SetsandIndependence in Semigroups.InternationalJournalofComputerScienceandMathematicalTheory(IJCSMT) E-ISSN 2545-5699 P-ISSN 2695-1924 Vol 10. No.1 2024 www.iiardjournals.org.
[15]Marshal I. S., EkereS. U., Igiri C., Effiong,L.E., EkeN. (2024). Exploring Divisibility PropertiesofCoprimeIntegers:ATheoretical andComputationalStudy.InternationalJournalofAppliedScienceandMathematicalTheoryE-ISSN2489-009X P-ISSN2695-1908,Vol.10No.1,2024.www.iiardjournals.org.
Published
2024-03-17
How to Cite
Marshal Imeh, S., Asuquo Efiong, F., John, E., & I. Okeke, S. (2024). ENHANCE CANONICAL IMAGE COMPUTATION FOR FINITE PERMUTATION GROUPS USING GRAPH BACKTRACKING. GPH - International Journal of Mathematics, 7(03), 19-33. https://doi.org/10.5281/zenodo.10827580
Issue
Vol 7 No 03 (2024): GPH - International Journal of Mathematics
Section
Articles
Copyright (c) 2024 1Sampson, Marshal Imeh, Felix Asuquo Efiong, Eno John, Stephen I. Okeke

Author(s) and co-author(s) jointly and severally represent and warrant that the Article is original with the author(s) and does not infringe any copyright or violate any other right of any third parties, and that the Article has not been published elsewhere. Author(s) agree to the terms that the GPH Journal will have the full right to remove the published article on any misconduct found in the published article.