{"entities":{"Q2336847":{"pageid":2347590,"ns":120,"title":"Item:Q2336847","lastrevid":57315339,"modified":"2026-03-30T09:40:55Z","type":"item","id":"Q2336847","labels":{"en":{"language":"en","value":"Novel techniques to speed up the computation of the automorphism group of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7131991"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$AECC80FE-0419-4E1C-A73D-2B4E6750FC1F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"59ea336f145525e36d0cbec1789620b22028e508","datavalue":{"value":{"text":"Novel techniques to speed up the computation of the automorphism group of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2336847$E63B2347-BAEF-4EB4-B277-6F66406EC944","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"84beafb4d3c9fea7f3d4a42a39918e6d0229cd7f","datavalue":{"value":"1442.05135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$CB7BA510-153F-4F74-A9A8-63A5662BEE98","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9d23118be0a0ed9238cfe2f67a96ebacdc7172ed","datavalue":{"value":"10.1155/2014/934637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$1A84CAEC-EB88-45F5-9679-E3EAE8899557","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7346d7761c60285a925183f771e521e0c1df1dad","datavalue":{"value":{"entity-type":"item","numeric-id":2009631,"id":"Q2009631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$4AD1BD49-0711-4160-8D89-C4FA7A8157B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8b1e867af33a4ca6bc543ae1f6ff76ee75afc5d","datavalue":{"value":{"entity-type":"item","numeric-id":2336846,"id":"Q2336846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$8A458256-FC14-4731-87CE-903C8BB781F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6f998033b531cb7063136d67fe05afc30545a95","datavalue":{"value":{"entity-type":"item","numeric-id":282237,"id":"Q282237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$1942DB5F-5AB6-4D25-ADCE-0BAE1E66B43F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bb299feb2b87699ac8beef494c52fd2765eaf609","datavalue":{"value":{"entity-type":"item","numeric-id":118601,"id":"Q118601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$D3CA783F-4783-467C-A71E-515ED84789EB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"10393ba55f1a886ba53e75eccd4b56403eff1eb9","datavalue":{"value":{"time":"+2019-11-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2336847$9CB395B4-61FF-4B83-8916-587ED1472176","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4f7d236e4805e0add34b10e79fa30624c71eb57d","datavalue":{"value":"Summary: 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 \\textit{conauto-2.03}, 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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2336847$6099A324-D5D2-4605-B85B-F4E5309073AF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$149F4E19-71FE-44FC-8407-BF0149F8C7EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$6691C787-301C-43B4-B0CE-81FE4539440E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$76F717E5-CE7B-4A5B-AE14-61A2E131F635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$A49232EC-1B43-4BB7-BAFD-41533F681839","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25c8936003d39e41a9c8a541470f5aac0fe1fa32","datavalue":{"value":"20B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$68A77035-3375-4BE6-B188-7E9AF4A6302A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"24ae4e59e85287fb5e6053b2cce93acc8099da3d","datavalue":{"value":"7131991","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$5F114F69-7F88-43E4-8835-3172D32D7C47","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"90f139681161cf03fca3b88a13657b8b8fd37862","datavalue":{"value":{"entity-type":"item","numeric-id":25180,"id":"Q25180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$2E1D3130-6E76-44B6-BF72-8FD52CEAB145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1b102a863af11783b12aae949286c5c2bf717c57","datavalue":{"value":{"entity-type":"item","numeric-id":25778,"id":"Q25778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$D3EF4434-4443-4FD9-BA65-B6EE86612AC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"545ef423157fa26cc9a4833f5ce4b40828f7875f","datavalue":{"value":{"entity-type":"item","numeric-id":38696,"id":"Q38696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$4D6DFB88-812D-42DC-B1C2-DAF19FFC67D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"58012661cd5902d08c1d307a106ffc22f40d0c6b","datavalue":{"value":{"entity-type":"item","numeric-id":13366,"id":"Q13366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$5EA90572-67A5-4333-82D1-38C12275D372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1ef314e7f189ae03dfc3388f96f819c0c665d6a2","datavalue":{"value":{"entity-type":"item","numeric-id":33598,"id":"Q33598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$C7727401-07EE-431C-B703-A794F5BE409D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1a2d88dbf6b03df258627eeae1776e81ae3634fd","datavalue":{"value":{"entity-type":"item","numeric-id":19839,"id":"Q19839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$89462BC5-00C1-4321-B0F5-108623C30E69","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$5A76E433-1202-421E-A688-85A3405DE9D5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0f306add361df4e4f03b60cdd59071e44c859f48","datavalue":{"value":"https://doi.org/10.1155/2014/934637","type":"string"},"datatype":"url"},"type":"statement","id":"Q2336847$637D6A15-949F-4425-9C75-73BFB17D3D59","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba02fb3d4df06ae1253d974d99cafe81c9af5347","datavalue":{"value":"W2096704006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$A0EACEC1-BA53-4F3E-A823-3D828EEBDC37","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2771d64dc963656ce96a217e3e9fd01e42414794","datavalue":{"value":"Q59054358","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336847$C1AE9707-CD37-45F5-B974-9507DBB11FC5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a556ebdf70d4dccab6829384fc6bfdcb4d3f1c3f","datavalue":{"value":{"entity-type":"item","numeric-id":3671211,"id":"Q3671211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$49119A38-3200-4159-A0DA-E722C7218B99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7d4a4f716519990f97bf8dc706e6f10261ef5af","datavalue":{"value":{"entity-type":"item","numeric-id":5233500,"id":"Q5233500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$8161C800-FC07-46E5-ABC2-405C71B658C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"088ba74fe9054b67645fc58dd8fe2654e7303708","datavalue":{"value":{"entity-type":"item","numeric-id":2999342,"id":"Q2999342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$7202DA49-4F4D-4BD0-A5E1-EBE3153FBF96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cb981fdc3238154c5fabc91203480f916f16d07","datavalue":{"value":{"entity-type":"item","numeric-id":3507262,"id":"Q3507262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$C3630A86-D32A-4C74-8FBE-44C9F13D9C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f646046f02cde628a0680327261c8770d27e5ab","datavalue":{"value":{"entity-type":"item","numeric-id":2437295,"id":"Q2437295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$11306D08-2EEA-4C7A-9A58-F0CFC2B6BA4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8c380d2417527e371b1f73a16a203d8d5efa1ca","datavalue":{"value":{"entity-type":"item","numeric-id":4930583,"id":"Q4930583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$1193D7DD-D772-4977-A195-076C75D5AA0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66ff6f5d0c049211bbb2b27735c772bc25d865fd","datavalue":{"value":{"entity-type":"item","numeric-id":2891455,"id":"Q2891455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$10DB1F39-943B-4561-A524-78A521DCCD6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"141794a00237295986f00275c27aee9706b73f5b","datavalue":{"value":{"entity-type":"item","numeric-id":1241450,"id":"Q1241450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$83821F66-1EFF-4939-AC31-F0A2638F1E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf3375a35d2d8d01fd7598ca171b1ec4b386b677","datavalue":{"value":{"entity-type":"item","numeric-id":4335302,"id":"Q4335302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$77066436-33ED-472E-BD00-5B24645F0FB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c4abf3db6829ace9384b6df6322b26d792dd48b","datavalue":{"value":{"entity-type":"item","numeric-id":1019607,"id":"Q1019607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$407E6A78-438B-42AA-85F9-234D7535AC15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65ac30b612ab6cd6e0da882a4820b600cf81fda9","datavalue":{"value":{"entity-type":"item","numeric-id":954962,"id":"Q954962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$89D2FE57-D9D4-4A30-AD0A-3EEA10AD27AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9211aa32d28b972b8ad4d67e0e77a7ef4c9f2309","datavalue":{"value":{"entity-type":"item","numeric-id":1123397,"id":"Q1123397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$BDCF6494-4708-4AD8-82C4-CA357B4CA327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70d0349d5918ee2f0bd4417db187ae279df98b28","datavalue":{"value":{"entity-type":"item","numeric-id":4417659,"id":"Q4417659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$356555EE-4513-4C1E-A0EA-8E4BB18DBE82","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb16fe417513ebb9b1e35774716e52810f265ce4","datavalue":{"value":{"entity-type":"item","numeric-id":675067,"id":"Q675067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08d0fa5602c8a3f7c8048e5fd91748308a49fbde","datavalue":{"value":{"amount":"+0.7709367871284485","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2336847$5CF71697-59C2-434C-BE2A-4B0C81D56253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c04cc650540b3e4575db4ca6d7fdf461f1797ad6","datavalue":{"value":{"entity-type":"item","numeric-id":3507262,"id":"Q3507262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a15ca09c6ca904af6d7d535a14f49b41639ea1b","datavalue":{"value":{"amount":"+0.7697039246559143","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2336847$B964E477-EAF9-4DE9-8EB0-65D977726381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ce11fd9b4d1caa03c8c15fdbf739476ba1a8893","datavalue":{"value":{"entity-type":"item","numeric-id":2999342,"id":"Q2999342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf2fd530f8836865b4c623c4b0383ef8ed3a7347","datavalue":{"value":{"amount":"+0.7608268857002258","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2336847$41FB5B67-5867-4CB1-BA65-07AA42219646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"139dfa6f975abfaf5973ddb6a9b79603028542fb","datavalue":{"value":{"entity-type":"item","numeric-id":2891455,"id":"Q2891455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b286b49a63a4d4359a4e5ec52efca03f07a53f0a","datavalue":{"value":{"amount":"+0.7488195300102234","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2336847$47950887-0394-4591-9819-23882D2501DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e8a8dbff243595045ba16de534f43dba762680d","datavalue":{"value":{"entity-type":"item","numeric-id":4335298,"id":"Q4335298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1f8d89c04dc77ebbf9033885b068e562bb58a14","datavalue":{"value":{"amount":"+0.7364937663078308","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2336847$1047EF7D-3B6A-438C-AFE5-2C74D987E091","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"daf5f856a5d861312ad309ab567540337a5f61d6","datavalue":{"value":{"entity-type":"item","numeric-id":57050,"id":"Q57050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336847$EFB9B55C-631E-4F1D-91AE-932B52E57CFC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2336847","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2336847"}}}}}