{"entities":{"Q5940668":{"pageid":8117470,"ns":120,"title":"Item:Q5940668","lastrevid":47656321,"modified":"2026-01-02T08:45:43Z","type":"item","id":"Q5940668","labels":{"en":{"language":"en","value":"Recognizing circulant graphs in polynomial time: An application of association schemes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1633286"}},"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":"Q5940668$FD39243F-DF9E-4118-AE64-E2EF271B811D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1cd2f3810aa2dd790fdf54fb0a0238fa4485ca7f","datavalue":{"value":{"text":"Recognizing circulant graphs in polynomial time: An application of association schemes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5940668$F909B36B-D91C-4C1D-97E5-66B4F096C057","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d2a21237826a7a4afe1eaeae7ad312e67b45d49","datavalue":{"value":"0996.05072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940668$F2821FEE-9C3B-473A-94B6-0B4093BADFFA","rank":"normal"}],"P16":[{"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":"Q5940668$BA815C25-3F29-4AA5-B8B5-2D9E4A217CDC","rank":"normal"},{"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":"Q5940668$615F9586-92F8-4AF9-994F-CC97F2E0A681","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":"Q5940668$D3F53A19-9701-481F-B125-9BD3E4035428","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0314b5a051dfeeb73cb27a5aea010a13792ac7cc","datavalue":{"value":{"time":"+2001-08-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":"Q5940668$F00B69B8-9F0B-45F5-B68E-6D5B3BE12A79","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"49db3dc5efc0b11f07313fae5dc93c98f3f6cf73","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i1r26.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q5940668$A919572E-DA68-4ABE-BF58-3E9DE351995C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e82f32c91e1eb0067a512f27a8cb077a4f29f958","datavalue":{"value":{"entity-type":"item","numeric-id":640843,"id":"Q640843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940668$02840B58-66B9-4968-A56F-ED89760B5251","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940668$4CF9D6DD-3E67-4CEF-A45D-2A37E174E115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940668$A025174A-4D4D-4D54-B0E6-40F6742EB2C0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d1714dc75b1c90e4f307c04ae6231cc68c87e101","datavalue":{"value":"1633286","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940668$72186468-E564-4F8D-B448-5A6CCA58928E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce7ab89ef0afcd2141c7da8aae338608bd16ac9a","datavalue":{"value":"automorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940668$286847FE-CE03-4362-91A7-B9720652C351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d18c7a8538f6670a7d99e3fee30616ac310b640","datavalue":{"value":"polynomial recognition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940668$60544F92-F70B-4192-9BBA-FB9B56AE0CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"838e316c2483ef64533e291f4a64eae5d7152e8e","datavalue":{"value":"circulant graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940668$886B4112-B251-49C7-8970-C3D4CF7FB3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39cd26dd3000f9596fa512b1cf137bbc1c017a95","datavalue":{"value":"Schur rings","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940668$42ECD586-0EF6-4677-A34D-FEF807B25C42","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":"Q5940668$51C27AAA-243C-4FE8-A9DA-3B3778CC11B6","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b02b07941dcb971d217a2beca684d4613cabacdb","datavalue":{"value":"bafkreieqtibqwg5slr5hibyhs2wtcrguamdk3uyhiiqa5bssnweds6jr7u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940668$50354A12-F384-4F3F-B28F-C79BEA621D3F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8a5afe8a5c52abd651ab2892102aab88a029c709","datavalue":{"value":"A graph \\(G\\) is circulant iff there is a cyclic permutation of the vertex set of \\(G\\) which is an automorphism of \\(G\\). In this paper a polynomial recognition algorithm for certain classes of circulant graphs is presented (the problem is to decide whether \\(G\\) is a circulant graph or not). The method for recognizing circulant graphs is based on the notions of coherent configurations and Schur rings generated by graphs and on the interrelations between these notions when the graph \\(G\\) has a cyclic automorphism.NEWLINENEWLINENEWLINEThe recognition problem for arbitrary circulant graphs is polynomially reducible to the recognition problem of circulant graphs induced by a generating set of the cyclic group which has trivial additive stabilizer. Geometric circulants and recursive geometric circulants are of special interest as models for interconnection networks.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940668$C3CA5B45-624A-42F0-904E-1B8BCB4E699F","rank":"normal"}],"P1643":[{"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":"6c5aaeedaec9354990cb6dce78667f28db8e1fee","datavalue":{"value":{"amount":"+0.8791921734809875","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":"Q5940668$6D56551D-F8D1-4C38-B2CD-730F74C3BE03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"361f8355aa47f5aebfe3f5ba3d65036e10f5b46f","datavalue":{"value":{"entity-type":"item","numeric-id":1386147,"id":"Q1386147"},"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":"Q5940668$E74D6BE9-009A-48CE-8D4F-32C756999745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90212339e0040d53c9169bf6c2e2936ec0a88bda","datavalue":{"value":{"entity-type":"item","numeric-id":724293,"id":"Q724293"},"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":"Q5940668$0BBC5A12-976F-4C1E-942E-A5408D142827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3278c61ccd5505eb0c13cd5dc2a606ecd79df99","datavalue":{"value":{"entity-type":"item","numeric-id":3022123,"id":"Q3022123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78e833887d46eb03bb6cbd51e7ae87b9108827a6","datavalue":{"value":{"amount":"+0.8323268294334412","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":"Q5940668$FA672C1B-9109-4360-AEAE-1B4EDC464E7E","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":"5e89eaf61e05a1151e3d8cb7c3a44823b502aaff","datavalue":{"value":{"amount":"+0.7795597314834595","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":"Q5940668$B9A81BE4-48D5-4187-9B03-E44F4384BDFB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5940668","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5940668"}}}}}