{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:31Z","timestamp":1750221091468,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T00:00:00Z","timestamp":1567641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>We describe five new algorithms, named Vsep. Four of them are for the graph automorphism group and the fifth one is for finding an isomorphism between two graphs. All nonequivalent terminal nodes-discrete partitions of the search tree are stored. This is the main difference of the exact version with the known algorithms for graph automorphism group. A new strategy is used in the exact algorithm: if during its execution the computed stabilizer orbits and order get wrong values, then the algorithm continues from a new starting point losing some of the results determined so far. The new starting point is such that the results are correct. The proposed algorithms have been tested on well-known benchmark graphs and compared with three of the most competitive known tools. The results show that for some graph families the exact Vsep algorithm outperforms these algorithms, and vice-versa for some of the others. None of the tested algorithms outperform others in all cases. The heuristic versions use reduced search trees. They are almost exact and are faster than the exact one with very rare exceptions. They are applied mainly for regular graphs. The heuristic algorithms are a new choice for the user. The experiments show that the running times of Vsep algorithms have a slight dependence on vertex labeling.<\/jats:p>","DOI":"10.1145\/3333250","type":"journal-article","created":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T12:14:48Z","timestamp":1567685688000},"page":"1-27","source":"Crossref","is-referenced-by-count":5,"title":["New Exact and Heuristic Algorithms for Graph Automorphism Group and Graph Isomorphism"],"prefix":"10.1145","volume":"24","author":[{"given":"Stoicho D.","family":"Stoichev","sequence":"first","affiliation":[{"name":"Technical University of Sofia, Sofia, Bulgaria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1974","unstructured":"Alfred V. Aho , John E. Hopcroft , and Jeffrey D . Ullman . 1974 . The Design and Analysis of Computer Algorithms (1st. ed.). Addison-Wesley . https:\/\/www.amazon.com\/Design-Analysis-Computer-Algorithms\/dp\/0201000296. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1974. The Design and Analysis of Computer Algorithms (1st. ed.). Addison-Wesley. https:\/\/www.amazon.com\/Design-Analysis-Computer-Algorithms\/dp\/0201000296."},{"key":"e_1_2_1_2_1","volume-title":"Abstract Algebra: The Basic Graduate Year. Nature","author":"Ash Robert B.","year":"1952","unstructured":"Robert B. Ash . 1952 . Abstract Algebra: The Basic Graduate Year. Nature . http:\/\/webs.ucm.es\/BUCM\/mat\/doc8358.pdf. Robert B. Ash. 1952. Abstract Algebra: The Basic Graduate Year. Nature. http:\/\/webs.ucm.es\/BUCM\/mat\/doc8358.pdf."},{"key":"e_1_2_1_3_1","volume-title":"Graph Isomorphism in Quasipolynomial Time. Retrieved","author":"Babai Laszlo","year":"2018","unstructured":"Laszlo Babai . {n.d.}. Graph Isomorphism in Quasipolynomial Time. Retrieved January 1, 2018 from https:\/\/arxiv.org\/abs\/1512.03547. Laszlo Babai. {n.d.}. Graph Isomorphism in Quasipolynomial Time. Retrieved January 1, 2018 from https:\/\/arxiv.org\/abs\/1512.03547."},{"key":"e_1_2_1_4_1","volume-title":"Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. Retrieved","author":"Berkholz Christoph","year":"2018","unstructured":"Christoph Berkholz , Paul Bonsma , and Martin Grohe . {n.d.}. Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. Retrieved January 1, 2018 from https:\/\/arxiv.org\/pdf\/1509.08251.pdf. Christoph Berkholz, Paul Bonsma, and Martin Grohe. {n.d.}. Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. Retrieved January 1, 2018 from https:\/\/arxiv.org\/pdf\/1509.08251.pdf."},{"key":"e_1_2_1_5_1","volume-title":"Colbourn","author":"Booth Kellogg S.","year":"1979","unstructured":"Kellogg S. Booth and Charles J . Colbourn . 1979 . Problems Polynomially Equivalent to Graph Isomorphism. Retrieved January 1, 2018 from https:\/\/cs.uwaterloo.ca\/research\/tr\/1977\/CS-77-04.pdf. Kellogg S. Booth and Charles J. Colbourn. 1979. Problems Polynomially Equivalent to Graph Isomorphism. Retrieved January 1, 2018 from https:\/\/cs.uwaterloo.ca\/research\/tr\/1977\/CS-77-04.pdf."},{"key":"e_1_2_1_6_1","volume-title":"Rivest","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen , Charles E. Leiserson , and Ronald L . Rivest . 2009 . Introduction to Algorithms (3rd ed.). MIT Press . http:\/\/ressources.unisciel.fr\/algoprog\/s00aaroot\/aa00module1\/res\/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. 2009. Introduction to Algorithms (3rd ed.). MIT Press. http:\/\/ressources.unisciel.fr\/algoprog\/s00aaroot\/aa00module1\/res\/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321556.321562"},{"key":"e_1_2_1_8_1","unstructured":"Jonathan L. Gross Jay Yellen and Ping Zhang (Eds.). 2013. Handbook of Graph Theory (2nd ed.). Chapman and Hall\/CRC. http:\/\/books.google.com\/books?id&equals;mKkIGIea_BkC.   Jonathan L. Gross Jay Yellen and Ping Zhang (Eds.). 2013. Handbook of Graph Theory (2nd ed.). Chapman and Hall\/CRC. http:\/\/books.google.com\/books?id&equals;mKkIGIea_BkC."},{"volume-title":"Graph Theory","author":"Harary Frank","key":"e_1_2_1_9_1","unstructured":"Frank Harary . 1977. Graph Theory . Addison-Wesley Publishing Company . www.dtic.mil\/dtic\/tr\/fulltext\/u2\/705364.pdf. Frank Harary. 1977. Graph Theory. Addison-Wesley Publishing Company. www.dtic.mil\/dtic\/tr\/fulltext\/u2\/705364.pdf."},{"key":"e_1_2_1_10_1","volume-title":"Lecture Notes in Computer Science","volume":"136","author":"Ed Christoph M.","year":"1982","unstructured":"Christoph M. Hoffmann ( Ed .). 1982 . Group-Theoretic Algorithms and Graph Isomorphism . Lecture Notes in Computer Science , Vol. 136 . Springer, Berlin. Christoph M. Hoffmann (Ed.). 1982. Group-Theoretic Algorithms and Graph Isomorphism. Lecture Notes in Computer Science, Vol. 136. Springer, Berlin."},{"key":"e_1_2_1_11_1","volume-title":"Implementations of 3 Types of the Schreier-Sims Algorithm. Retrieved","author":"Jaggi Martin","year":"2018","unstructured":"Martin Jaggi . 2005. Implementations of 3 Types of the Schreier-Sims Algorithm. Retrieved January 1, 2018 from https:\/\/www.m8j.net\/data\/List\/Files-118\/Documentation.pdf. Martin Jaggi. 2005. Implementations of 3 Types of the Schreier-Sims Algorithm. Retrieved January 1, 2018 from https:\/\/www.m8j.net\/data\/List\/Files-118\/Documentation.pdf."},{"key":"e_1_2_1_12_1","unstructured":"William Kocay. {n.d.}. Groups8Graphs. Retrieved January 1 2018 from http:\/\/www.combinatorialmath.ca\/G8G\/.  William Kocay. {n.d.}. Groups8Graphs. Retrieved January 1 2018 from http:\/\/www.combinatorialmath.ca\/G8G\/."},{"key":"e_1_2_1_13_1","volume-title":"Stinson","author":"Kreher Donald L.","year":"1998","unstructured":"Donald L. Kreher and Douglas R . Stinson . 1998 . Combinatorial Algorithms : Generation, Enumeration, and Search. CRC Press . http:\/\/www2.denizyuret.com\/bib\/kreher\/donald1999combinatorial\/combinatorialA.pdf. Donald L. Kreher and Douglas R. Stinson. 1998. Combinatorial Algorithms: Generation, Enumeration, and Search. CRC Press. http:\/\/www2.denizyuret.com\/bib\/kreher\/donald1999combinatorial\/combinatorialA.pdf."},{"key":"e_1_2_1_14_1","volume-title":"Luis Nunez Chiroque, and Antonio Fernandez Anta","author":"Lopez-Presa Jose Luis","year":"2014","unstructured":"Jose Luis Lopez-Presa , Luis Nunez Chiroque, and Antonio Fernandez Anta . 2014 . Novel techniques to speed up the computation of the automorphism group of a graph. Hindawi Publishing Corporation Journal of Applied Mathematics (July 2014). https:\/\/www.hindawi.com\/journals\/jam\/2014\/934637\/. Jose Luis Lopez-Presa, Luis Nunez Chiroque, and Antonio Fernandez Anta. 2014. Novel techniques to speed up the computation of the automorphism group of a graph. Hindawi Publishing Corporation Journal of Applied Mathematics (July 2014). https:\/\/www.hindawi.com\/journals\/jam\/2014\/934637\/."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 9th Southeastern Conference on Combinatorics, Graph Theory, and Computing. 499--517","author":"Mathon Rudolf","year":"1978","unstructured":"Rudolf Mathon . 1978 . Sample graphs for isomorphism testing . In Proceedings of the 9th Southeastern Conference on Combinatorics, Graph Theory, and Computing. 499--517 . Rudolf Mathon. 1978. Sample graphs for isomorphism testing. In Proceedings of the 9th Southeastern Conference on Combinatorics, Graph Theory, and Computing. 499--517."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90004-8"},{"key":"e_1_2_1_17_1","volume-title":"Congressus Numerantium 30","author":"McKay Brendan D.","year":"1981","unstructured":"Brendan D. McKay . 1981 . Practical graph isomorphism . Congressus Numerantium 30 (1981), 45--87. http:\/\/users.cecs.anu.edu.au\/&sim;bdm\/nauty\/pgi.pdf. Brendan D. McKay. 1981. Practical graph isomorphism. Congressus Numerantium 30 (1981), 45--87. http:\/\/users.cecs.anu.edu.au\/&sim;bdm\/nauty\/pgi.pdf."},{"key":"e_1_2_1_18_1","volume-title":"McKay and Adolfo Piperno. {n.d.}. nauty and Traces Website. Retrieved","author":"Brendan","year":"2018","unstructured":"Brendan D. McKay and Adolfo Piperno. {n.d.}. nauty and Traces Website. Retrieved January 1, 2018 from http:\/\/pallini.di.uniroma1.it\/. Brendan D. McKay and Adolfo Piperno. {n.d.}. nauty and Traces Website. Retrieved January 1, 2018 from http:\/\/pallini.di.uniroma1.it\/."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_20_1","unstructured":"M. I. Nechepurenko V. K. Popkov S. M. Mayagashev S. B. Kaul V. A. Proskuryakov V. A. Kokhov and A. B. Gryzunov. 1990. Algorithms and Programs for Solving Problems on Graphs and Networks. Nauka Novosibirsk. http:\/\/mt3.org\/bloog\/wodolaz\/39.html.  M. I. Nechepurenko V. K. Popkov S. M. Mayagashev S. B. Kaul V. A. Proskuryakov V. A. Kokhov and A. B. Gryzunov. 1990. Algorithms and Programs for Solving Problems on Graphs and Networks. Nauka Novosibirsk. http:\/\/mt3.org\/bloog\/wodolaz\/39.html."},{"key":"e_1_2_1_21_1","volume-title":"Toward effective algorithms for linear groups. Finite Geometries, Groups, and Computation","author":"O\u2019Brien E. A.","year":"2006","unstructured":"E. A. O\u2019Brien . 2006. Toward effective algorithms for linear groups. Finite Geometries, Groups, and Computation ( 2006 ), 163--190. https:\/\/www.math.auckland.ac.nz\/&sim;obrien\/research\/survey.pdf. E. A. O\u2019Brien. 2006. Toward effective algorithms for linear groups. Finite Geometries, Groups, and Computation (2006), 163--190. https:\/\/www.math.auckland.ac.nz\/&sim;obrien\/research\/survey.pdf."},{"key":"e_1_2_1_22_1","unstructured":"Stoicho D. Stoichev. {n.d.}. Stoicho D. Stoichev\u2019s Website. Retrieved January 1 2018 from https:\/\/sites.google.com\/site\/stoichostoichev2\/home.  Stoicho D. Stoichev. {n.d.}. Stoicho D. Stoichev\u2019s Website. Retrieved January 1 2018 from https:\/\/sites.google.com\/site\/stoichostoichev2\/home."},{"key":"e_1_2_1_23_1","volume-title":"Vsep-New Heuristic and Exact Algorithms for Graph Automorphism Group Computation. Retrieved","author":"Stoichev Stoicho D.","year":"2018","unstructured":"Stoicho D. Stoichev . {n.d.}. Vsep-New Heuristic and Exact Algorithms for Graph Automorphism Group Computation. Retrieved January 1, 2018 from https:\/\/arxiv.org\/abs\/1007.1726. Stoicho D. Stoichev. {n.d.}. Vsep-New Heuristic and Exact Algorithms for Graph Automorphism Group Computation. Retrieved January 1, 2018 from https:\/\/arxiv.org\/abs\/1007.1726."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Digital Signal Processing","volume":"2","author":"Stoichev Stoicho D.","year":"1995","unstructured":"Stoicho D. Stoichev . 1995 . Fast adjacency refinement algorithm . In Proceedings of the International Conference on Digital Signal Processing , Limassol, Cyprus , Vol. 2 . 870--875. Stoicho D. Stoichev. 1995. Fast adjacency refinement algorithm. In Proceedings of the International Conference on Digital Signal Processing, Limassol, Cyprus, Vol. 2. 870--875."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3333250","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3333250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:57Z","timestamp":1750208277000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3333250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,5]]},"references-count":24,"alternative-id":["10.1145\/3333250"],"URL":"https:\/\/doi.org\/10.1145\/3333250","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2019,9,5]]}}}