ENHANCE CANONICAL IMAGE COMPUTATION FOR FINITE PERMUTATION GROUPS USING GRAPH BACKTRACKING
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
References
[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.
The authors and co-authors warrant that the article is their original work, does not infringe any copyright, and has not been published elsewhere. By submitting the article to GPH - International Journal of Mathematics, the authors agree that the journal has the right to retract or remove the article in case of proven ethical misconduct.
