{"entities":{"Q1911841":{"pageid":1922583,"ns":120,"title":"Item:Q1911841","lastrevid":46424151,"modified":"2025-12-24T18:32:01Z","type":"item","id":"Q1911841","labels":{"en":{"language":"en","value":"On the complexity of recognizing Hamming graphs and related classes of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 871016"}},"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":"Q1911841$B92E04B3-CB91-47EE-80E1-C3D5E9A4F6ED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"094bf214b848a0060a748b8df71382b144ddc7a3","datavalue":{"value":{"text":"On the complexity of recognizing Hamming graphs and related classes of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1911841$D539C66C-7E54-49EA-AEF5-4B1AB4FB1626","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"74df5c12133e70b8af091c13aed8033ce08f34ec","datavalue":{"value":"0846.05082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1911841$8657D2D7-73BD-4464-BA1E-63B14054E78D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"10c07f8b7e3cd9f2923ddf5077d5a80431b6d4ef","datavalue":{"value":{"entity-type":"item","numeric-id":201986,"id":"Q201986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1911841$1FEAEC8C-6139-45F8-AA9B-9A5F05910DCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ceb1fcf1c75dc367d934ec93f0fd1abaa5c7756","datavalue":{"value":{"entity-type":"item","numeric-id":251101,"id":"Q251101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1911841$85A8FCFB-1FDD-4A0A-A69E-309FD4422F8A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1911841$2B6FFF49-D021-4945-B29D-737B381FC05E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e8bc2e68a7a4ba958744d9a0d3480daad10515d7","datavalue":{"value":{"time":"+1996-07-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1911841$F7AAD9AD-C410-4E3F-95F5-EDAA9972437F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba14c35f939d0d3ee848a5e385e9d2ab4d1f5535","datavalue":{"value":"The authors survey recognition algorithms for Hamming graphs (i.e. Cartesian products of complete graphs), retracts of Hamming graphs and isometric subgraphs of Hamming graphs. The paper also contains a new algorithm that recognizes whether a given graph \\(G= (V, E)\\) is a Hamming graph in \\(O(|E|)\\) time and \\(O(|V|^2)\\) space.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1911841$F57102FD-9721-44C2-894F-10B8449B4364","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4fefa17be9d4bfc1a51cd1d93e86e23724d8c0a1","datavalue":{"value":{"entity-type":"item","numeric-id":168084,"id":"Q168084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1911841$AB6C957C-1014-46E4-988A-0152D21AE998","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1911841$BF567249-B07E-4765-A22E-6677C8B53CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1911841$6E8883BC-B3F1-413D-95AD-F4AF783B8BD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1911841$208E73A1-2B96-4E13-9712-02B10CB3D0C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1911841$3670F969-4315-4B36-9A8D-B5878DD32978","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6114df6a566719aadc3885e54719ce60d3090282","datavalue":{"value":"871016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1911841$6BAC970F-9848-4C1A-A3BA-DE1D27E1BC51","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1911841$22E94E91-585F-4AF8-BAF3-F1AF98E004A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8de0f0c5e02cd0505a6f3655182209c90c31101a","datavalue":{"value":"recognition algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1911841$788F255F-B362-4847-B735-D329A1EDB4AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"007b8aeb89dd560653043bc94d13df946bb1c8be","datavalue":{"value":"Hamming graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1911841$ABC78E37-A9FE-4E37-AC84-33490C6085EC","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":"Q1911841$BF6DFB67-E5B5-41FE-B85A-23ED2A10C8CB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"93cc0075090ccb618f143426db3f270cbdc90081","datavalue":{"value":"https://doi.org/10.1006/eujc.1996.0018","type":"string"},"datatype":"url"},"type":"statement","id":"Q1911841$42A61E40-A0A3-47D6-B9F7-6175B9754C57","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"46ba01cb7a735f83b5d101daca5a38403e9f1591","datavalue":{"value":"W2043736547","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1911841$F7762CFB-7001-42A4-BF4E-459933F3B2BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a1a744230d0eea6b516e63276727cb6132354c8","datavalue":{"value":"10.1006/EUJC.1996.0018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1911841$2E1026D2-DB08-4426-BF85-2DA9B7104B1D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5aec6ccae41c278a95a39cf0a756e469d0aa8e0f","datavalue":{"value":{"entity-type":"item","numeric-id":287143,"id":"Q287143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d81275280de9b1ea14abe2375ab5b6d8e09bf9a9","datavalue":{"value":{"amount":"+0.8896455764770508","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":"Q1911841$3F372506-721A-4068-9D0A-913C5F78EBB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82ff31197e230b911d0bc008cb68498341ff5629","datavalue":{"value":{"entity-type":"item","numeric-id":4309135,"id":"Q4309135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69e652e04b9829751f048934ec76e2b392542c2b","datavalue":{"value":{"amount":"+0.8791636824607849","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":"Q1911841$7C2C07D4-1663-4A11-BB9A-6D8596818617","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dffd615596c3dba7f30f2176e36ff5fba2611df","datavalue":{"value":{"entity-type":"item","numeric-id":1110526,"id":"Q1110526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"147bcc2d632d3007cd81c31414f3820b9e092a92","datavalue":{"value":{"amount":"+0.8206554651260376","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":"Q1911841$DCDD31E1-484B-4DA7-992E-2562C258A8BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74ab4dcc435b000f69d4c04503921d309094da48","datavalue":{"value":{"entity-type":"item","numeric-id":3734453,"id":"Q3734453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"422a96f8746a1a694d7b6cf5afbb46ec7a53618b","datavalue":{"value":{"amount":"+0.8134090900421143","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":"Q1911841$2C7F6121-DAC6-455A-A27B-BE5DE662F903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"685f718563835f01c821a4fb84d04f3186dc4906","datavalue":{"value":{"entity-type":"item","numeric-id":4028106,"id":"Q4028106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34ae4a94eb46b45f08a5b757d765c57926e62aec","datavalue":{"value":{"amount":"+0.8106062412261963","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":"Q1911841$CC818A09-FDCE-42B7-8325-CADC9142C8D8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1911841","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1911841"}}}}}