{"entities":{"Q1386147":{"pageid":1396887,"ns":120,"title":"Item:Q1386147","lastrevid":67452651,"modified":"2026-04-12T17:59:28Z","type":"item","id":"Q1386147","labels":{"en":{"language":"en","value":"Recognizing circulant graphs of prime order in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1151634"}},"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":"Q1386147$F2CEED8D-018D-44F9-A799-5B2F548C49A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2db1925270e91f578f2951249e45e02be5c05d69","datavalue":{"value":{"text":"Recognizing circulant graphs of prime order in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1386147$9B2ABFE2-EDE5-492E-834B-9CC7AEEF155F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4a76c33e186e8edac6ac6e46c9c6bc5b04bff68d","datavalue":{"value":"0901.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386147$046E1A64-9A68-4725-A535-CC69188023D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a04ecc81832bff993b189ec55412cfe64658861b","datavalue":{"value":{"entity-type":"item","numeric-id":196797,"id":"Q196797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386147$4C1BA890-B3B6-4749-919E-977CF7D64EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0080982d92245a44504131c3ac32d506b9c2ad4","datavalue":{"value":{"entity-type":"item","numeric-id":633277,"id":"Q633277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386147$07AAC6BF-49B7-4E79-895A-57B90DBFF211","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386147$66307B33-734A-4EE9-B3F9-B22EE8338D68","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"02e0ea8672a19da323d4689ae7e1a0c87afc535f","datavalue":{"value":{"time":"+1998-05-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1386147$DF46EA1E-0C7C-496E-BF51-5CF5EB7CBC20","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dbdaa60c3a628b2ce5985b3005b2f78bb8d7447f","datavalue":{"value":"https://eudml.org/doc/119615","type":"string"},"datatype":"url"},"type":"statement","id":"Q1386147$AEEA81B5-DA30-4B4A-86E7-5FCB4E6423D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"bb8b1efb2812bff5c299ed6821e545f25f92f238","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_5/Abstracts/v5i1r25.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1386147$08689E06-59D4-4345-A9CB-7593DDF1A995","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21bbfeadcb1f94ee71a6aabc8f1e7fe12cd16bbb","datavalue":{"value":"A digraph can be regarded as a pair \\((X;\\gamma)\\), where \\(X\\) is a finite set and \\(\\gamma\\) is a binary relation on \\(X\\). The Weisfeiler-Leman algorithm in time \\(O(| X|^3\\log(| X|))\\) yields the minimal coherent configuration \\((X;\\Gamma)\\), where \\(\\Gamma\\) contains \\(\\gamma\\) [\\textit{Babel, Baumann, L\u00fcdecke} and \\textit{Tinhofer}, STABCOL: Graph isomorphism testing based on the Weisfeiler-Leman algorithm. TUM-M9702, Munich, 45 p. (1997)]. There is an open problem to recognize the circulant property of digraphs \\(X\\) with an algorithm with time-complexity polynomial in \\(X\\). The authors present such an algorithm when \\(| X| = p\\), a prime, with time-complexity at most \\(O(p^5\\ln(p)^2)\\). They start with the above coherent configuration (in this case, association scheme), and then utilize favorable facts on permutation groups and association schemes when \\(| X|\\) is a prime \\(p\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386147$FF77F578-4816-40E2-9FBE-45CED56E3827","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386147$4D7EDC0E-7109-47A5-A840-BC38F1E727E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386147$8B7B592B-BBD4-4CEA-814E-2032BFD1850A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"98259a5dd4d8db83a95d10edc3bf87986357d020","datavalue":{"value":"05E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386147$FB64055F-C663-40A2-B4A2-60399A2F97C9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1458dcc80724daa6f868b05de6673dd27ea3bba1","datavalue":{"value":"1151634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386147$6D236149-6A01-4D46-AD41-482B71407D9C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7decde45aa28f7520212fb84cab816519940f4c9","datavalue":{"value":"recognition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386147$A096B509-20F6-488F-9890-EE8400D2F46E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"949b0c2ed048a2b62cbf3d95fd8f3cae888908d6","datavalue":{"value":"circulant graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386147$CF952A43-771B-4FAD-8D5D-65029C4B0417","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb41184b4eb43658517e36f0c87e148c155cd9db","datavalue":{"value":"cyclic association scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386147$9C58EC5D-FA68-447C-A42A-EDCA4B124C5D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"64817b52ac7d6f6e6e0eb7e4b49d45a91d54882b","datavalue":{"value":{"entity-type":"item","numeric-id":1053696,"id":"Q1053696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386147$AAF5F8B9-125D-4B49-A061-6B47CF763303","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":"Q1386147$C104318F-C792-48CA-9264-4F9C2D62FCAF","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"0ec62b1b9eda9a6a997fe9af97f0a0b01b55d636","datavalue":{"value":"bafkreidyluunayz4ug4xjx2jbya4q533fdijcky3v67us3uvbopmtfpz5q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386147$5395DB1F-D39C-491C-954A-1119BFF11031","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97d382ae122518f91a544ec74d638ee2d545eed3","datavalue":{"value":{"entity-type":"item","numeric-id":5940668,"id":"Q5940668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ddcc339c5ea9e7da43baf59cd12bf4d44669c23","datavalue":{"value":{"amount":"+0.8407886028289795","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":"Q1386147$91589205-8011-4A61-BEE2-A2EA93AB79AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fcd600b3a4f9cf789a6f2c9749a05a78503c48e","datavalue":{"value":{"entity-type":"item","numeric-id":4675535,"id":"Q4675535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a7c59cb45cfd3b2707d33abc6401d5a847d6905","datavalue":{"value":{"amount":"+0.825083315372467","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":"Q1386147$45BF9EC3-CC95-4B58-8F61-AE5C7A7A55CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23716a85cb220613cca8304a0e96fbf4b9820c98","datavalue":{"value":{"entity-type":"item","numeric-id":4460731,"id":"Q4460731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8bda83bdd4db2975167fe1846bfb72e195996db","datavalue":{"value":{"amount":"+0.771364152431488","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":"Q1386147$BB9D0160-CC90-4744-B463-36DAF4D194A8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recognizing circulant graphs of prime order in polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Recognizing_circulant_graphs_of_prime_order_in_polynomial_time"}}}}}