{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T16:24:41Z","timestamp":1761841481754,"version":"3.37.3"},"reference-count":17,"publisher":"Wiley","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"DOI":"10.13039\/100012818","name":"Comunidad de Madrid","doi-asserted-by":"crossref","award":["2009TIC-1692","TEC2011-29688-C02-01","61020106002"],"award-info":[{"award-number":["2009TIC-1692","TEC2011-29688-C02-01","61020106002"]}],"id":[{"id":"10.13039\/100012818","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003329","name":"Ministry of Economy and Competitiveness","doi-asserted-by":"crossref","award":["2009TIC-1692","TEC2011-29688-C02-01","61020106002"],"award-info":[{"award-number":["2009TIC-1692","TEC2011-29688-C02-01","61020106002"]}],"id":[{"id":"10.13039\/501100003329","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["2009TIC-1692","TEC2011-29688-C02-01","61020106002"],"award-info":[{"award-number":["2009TIC-1692","TEC2011-29688-C02-01","61020106002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Applied Mathematics"],"published-print":{"date-parts":[[2014]]},"abstract":"<jats:p>Graph automorphism (GA) is a classical problem, in which the objective is to compute the automorphism group of an input graph. Most GA algorithms explore a search tree using the individualization-refinement procedure. Four novel techniques are proposed which increase the performance of any algorithm of this type by reducing the depth of the search tree and by effectively pruning it. We formally prove that a GA algorithm that uses these techniques correctly computes the automorphism group of an input graph. Then, we describe how these techniques have been incorporated into the GA algorithm conauto, as<jats:italic>conauto-2.03<\/jats:italic>, with at most an additive polynomial increase in its asymptotic time complexity. Using a benchmark of different graph families, we have evaluated the impact of these techniques on the size of the search tree, observing a significant reduction both when they are applied individually and when all of them are applied together. This is also reflected in a reduction of the running time, which is substantial for some graph families. Finally, we have compared the search tree size of conauto-2.03 against those of other popular GA algorithms, observing that, in most cases, conauto explores less nodes than these algorithms.<\/jats:p>","DOI":"10.1155\/2014\/934637","type":"journal-article","created":{"date-parts":[[2014,7,24]],"date-time":"2014-07-24T22:02:55Z","timestamp":1406239375000},"page":"1-15","source":"Crossref","is-referenced-by-count":6,"title":["Novel Techniques to Speed Up the Computation of the Automorphism Group of a Graph"],"prefix":"10.1155","volume":"2014","author":[{"given":"Jos\u00e9 Luis","family":"L\u00f3pez-Presa","sequence":"first","affiliation":[{"name":"DIATEL-UPM, 28031 Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luis F.","family":"Chiroque","sequence":"additional","affiliation":[{"name":"IMDEA Networks Institute, 28918 Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio","family":"Fern\u00e1ndez Anta","sequence":"additional","affiliation":[{"name":"IMDEA Networks Institute, 28918 Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","reference":[{"issue":"3","key":"5","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1021\/ci9702914","volume":"38","year":"1998","journal-title":"Journal of Chemical Information and Computer Sciences"},{"key":"15","first-page":"45","volume":"30","year":"1981","journal-title":"Congressus Numerantium"},{"year":"2010","key":"16"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19754-3_16"},{"key":"20"},{"key":"23","first-page":"203","volume":"64","year":"2008","journal-title":"Journal of Combinatorial Mathematics and Combinatorial Computing"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/978-3-642-14186-7_11","volume-title":"Symmetry and satisfiability: an update","volume":"6175","year":"2010"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28717-6_20"},{"key":"11","series-title":"EPiC Series","first-page":"181","volume-title":"Graph symmetry detection and canonical labeling: differences and synergies","volume":"10","year":"2012"},{"volume":"558","year":"1976","series-title":"Lecture Notes in Mathematics","key":"25"},{"key":"18","first-page":"239","volume-title":"The complexity of McKay's canonical labeling algorithm","volume":"28","year":"1997"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_21"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.01.002"},{"year":"2011","key":"13"},{"year":"2009","key":"6"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(02)00253-2"}],"container-title":["Journal of Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/jam\/2014\/934637.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/jam\/2014\/934637.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/jam\/2014\/934637.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,12]],"date-time":"2020-05-12T03:11:21Z","timestamp":1589253081000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.hindawi.com\/journals\/jam\/2014\/934637\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"references-count":17,"alternative-id":["934637","934637"],"URL":"https:\/\/doi.org\/10.1155\/2014\/934637","relation":{},"ISSN":["1110-757X","1687-0042"],"issn-type":[{"type":"print","value":"1110-757X"},{"type":"electronic","value":"1687-0042"}],"subject":[],"published":{"date-parts":[[2014]]}}}