{"entities":{"Q666533":{"pageid":668382,"ns":120,"title":"Item:Q666533","lastrevid":63411279,"modified":"2026-04-11T12:47:44Z","type":"item","id":"Q666533","labels":{"en":{"language":"en","value":"A convex relaxation bound for subgraph isomorphism"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6013086"}},"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":"Q666533$ED0F61F4-A4A4-4251-A97E-B25E9B6661C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b389809e642e46beb2fed10ec1cadb2fc58054c4","datavalue":{"value":{"text":"A convex relaxation bound for subgraph isomorphism","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q666533$870CC5B5-87C7-426D-86AC-41F7B4532A0A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a90563a87579b4187ce02d2aee38e0ac26a784e0","datavalue":{"value":"1236.05133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666533$DF720975-B0CE-4B55-B4DB-2CB1D8245113","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"22bab45607c4ae791461cf4182f9c7b54c738bea","datavalue":{"value":"10.1155/2012/908356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666533$24123964-0D39-469D-9EFB-8FA4167B445C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d99025ae081da4e4b90d1805057b21b1244cfb1c","datavalue":{"value":{"entity-type":"item","numeric-id":666532,"id":"Q666532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$4DABF793-C9AE-4371-98A7-1555F2FE1105","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"12a0098946843c502c4d744c7c2f393983e21a01","datavalue":{"value":{"entity-type":"item","numeric-id":274754,"id":"Q274754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$5912BE37-BFCF-4409-824B-FA6382BF1CAE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"086baaac6cfff2b3761aa8ffbeed776449d2b918","datavalue":{"value":{"time":"+2012-03-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q666533$415A049B-DA9B-494C-87AF-5BA5E29F399F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"167da6bd9efecc75ede8994bf1343400812dcdcb","datavalue":{"value":"Summary: In this work a convex relaxation of a subgraph isomorphism problem is proposed, which leads to a new lower bound that can provide a proof that a subgraph isomorphism between two graphs can not be found. The bound is based on a semidefinite programming relaxation of a combinatorial optimisation formulation for subgraph isomorphism and is explained in detail. We consider subgraph isomorphism problem instances of simple graphs which means that only the structural information of the two graphs is exploited and other information that might be available (e.g., node positions) is ignored.    The bound is based on the fact that a subgraph isomorphism always leads to zero as lowest possible optimal objective value in the combinatorial problem formulation. Therefore, for problem instances with a lower bound that is larger than zero this represents a proof that a subgraph isomorphism can not exist. But note that conversely, a negative lower bound does not imply that a subgraph isomorphism must be present and only indicates that a subgraph isomorphism can not be excluded. In addition, the relation of our approach and the reformulation of the largest common subgraph problem into a maximum clique problem is discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q666533$63540F56-AFF8-4B9F-BA81-5F0A1221853A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666533$21DAA332-123C-4798-890F-09CBCDC0B3A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666533$EC4E8EB9-098B-482A-B99E-0117362DFEA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666533$791A0031-6041-4006-BA72-782CA9754E9F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d6809e98c86cc83f8aa51b41ad95898b7489ecfb","datavalue":{"value":"6013086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666533$1DBD5034-09CD-436D-9EFC-9814F450E103","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7553ab436535948893b127a8d3473cd75d119704","datavalue":{"value":"combinatorial optimization problem, Error-correcting graph matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q666533$D4FF43D6-A8C7-44EE-A2A4-B413DFFAEFBE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d09a7441cf37157f96cc1f681c9fe2ebc96f7ac3","datavalue":{"value":{"entity-type":"item","numeric-id":16788,"id":"Q16788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$A5D1D714-C0D6-4286-983E-FFF2A0C85A75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d13980459114061cccdbdebecd7eaa88ca0971b4","datavalue":{"value":{"entity-type":"item","numeric-id":4085764,"id":"Q4085764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$1D519C3E-054D-4384-9D3B-1A75C2661B1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea01f220092e831a692964f404f335297466e14a","datavalue":{"value":{"entity-type":"item","numeric-id":1245239,"id":"Q1245239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$2077A0BE-0074-4504-9597-CB396D49E7E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6327224c4debc2501c4439bfd0d53425e1e3cd69","datavalue":{"value":{"entity-type":"item","numeric-id":4505015,"id":"Q4505015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$B7BFC25D-FFB4-4007-AB60-8A21C43E4D21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0994b377a2f1ce023f04747d3ab2802f131254c9","datavalue":{"value":{"entity-type":"item","numeric-id":4749230,"id":"Q4749230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$255AEBAB-7196-4A8E-9F0A-88E0CB63A56D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fc05c055d041ba86074ddc1384be9190d0365f9","datavalue":{"value":{"entity-type":"item","numeric-id":5915427,"id":"Q5915427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$77E38DD3-5F7D-4D5F-B75C-4EF1A057D669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7f992e855d8b9b42f253fc7f7d98a5e06e39cb4","datavalue":{"value":{"entity-type":"item","numeric-id":4369893,"id":"Q4369893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$7AA366CA-F0EC-40A0-83DF-870126EECF53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22c12b3224da32986a1d27a1e88ce0fb7c6f0325","datavalue":{"value":{"entity-type":"item","numeric-id":4449678,"id":"Q4449678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$D486CC67-7B13-4791-9FDF-2F19C5AA91B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"525372ed24f37d00f0f443020d11b47093e622c3","datavalue":{"value":{"entity-type":"item","numeric-id":5316491,"id":"Q5316491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$E53E654A-E7D7-4C87-B7D0-BAB2A0B3F8B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfa0180fc07b01b5b3a63dd32f85d22b496fa0f3","datavalue":{"value":{"entity-type":"item","numeric-id":3145799,"id":"Q3145799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$8649304A-F4FE-4669-86B5-EBAC7B94AFFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$97DB3777-E5A6-4485-9FED-AEBB8057F720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ca263fbbb5b5d88e12729380f2dec9703dc4229","datavalue":{"value":{"entity-type":"item","numeric-id":1177910,"id":"Q1177910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$2AECC56C-9778-4B19-A6CE-989A66E777B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24b8a50da73502cd2d3d27896357e4e3127ec48f","datavalue":{"value":{"entity-type":"item","numeric-id":4504795,"id":"Q4504795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$449E422E-B231-4FCF-AA37-B05C57970B81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cff8a2dec28af71db12f7ba84a0550b875c8bdb","datavalue":{"value":{"entity-type":"item","numeric-id":4464638,"id":"Q4464638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$B3608A50-F405-4676-9018-A9C8087AF715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2b9883dba6760c4e6629f5ea3f1cec515574ce","datavalue":{"value":{"entity-type":"item","numeric-id":3812479,"id":"Q3812479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$F5DC8870-0421-4033-A8CD-2355B7FFBDC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c5f759d98b3881e72425ecd43593829b19ea420","datavalue":{"value":{"entity-type":"item","numeric-id":4382667,"id":"Q4382667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$3262D55A-BE26-41FE-B0B9-78FF1F0E7D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"681d3c499a790e8d671c36edc0c71ef77f4972ae","datavalue":{"value":{"entity-type":"item","numeric-id":1411647,"id":"Q1411647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$03B12889-514F-4460-8B9A-AA8C48748E19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bb04bfd976a3c8b3ace02065763ba44f1a8a718","datavalue":{"value":{"entity-type":"item","numeric-id":4884041,"id":"Q4884041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$B1E2438F-5026-42D5-A760-64ACE4D1E528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04fc1595a81247caed2e4ec616f59db6a77379e3","datavalue":{"value":{"entity-type":"item","numeric-id":4504794,"id":"Q4504794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$F597F977-BD0F-4E60-B258-31F05ACC2839","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ed98473e44c491620fb876f1930af595db4edae","datavalue":{"value":{"entity-type":"item","numeric-id":1811073,"id":"Q1811073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$E97367F5-601E-4E10-9588-B2F3BE26F5DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dcb4446087c3a1009df708ef3a2f3c1f3932cad","datavalue":{"value":{"entity-type":"item","numeric-id":5338788,"id":"Q5338788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$28EC4BA1-7BED-4E4A-A8BC-9E14DE8B78CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4dc7334961b783753cae28bdf4485be49788e86","datavalue":{"value":{"entity-type":"item","numeric-id":4218487,"id":"Q4218487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$E99F13D3-5EE7-4A1D-B48E-5E982A961226","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"bdf2d88fbe1aca9b237f60a6a6b629783d846e5b","datavalue":{"value":{"entity-type":"item","numeric-id":16788,"id":"Q16788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$DFCEDF6D-5855-4D01-8DC3-3F42FCB46293","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"163252dbef1171974de7ba4a960e3d47d319b144","datavalue":{"value":{"entity-type":"item","numeric-id":16515,"id":"Q16515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$9E44EB20-56A5-42E6-97A6-E7DE3ED21F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"33789359f9b960afff5924d56436a42c169171df","datavalue":{"value":{"entity-type":"item","numeric-id":12937,"id":"Q12937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666533$7F4C3909-D917-4D3E-B187-2AEC6A4839B2","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":"Q666533$500678E0-90A5-411B-B548-C76132E74FD8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1ccb4666590d3fa798ac0cc37bd4ba8a410ee08d","datavalue":{"value":"https://doi.org/10.1155/2012/908356","type":"string"},"datatype":"url"},"type":"statement","id":"Q666533$7F5E9C03-DEFF-4DC0-8C6E-984A089C2B82","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5af2a79d78dfa82d6dd0d120d8815f2cd1face93","datavalue":{"value":"W1966242563","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666533$D5B48BF0-8C09-472F-84FB-2C5AF0B98100","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d007f870feddc14ea69ac8b7a48722d4d376aea4","datavalue":{"value":"Q58703379","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666533$79FAE9DC-F661-4026-90D4-0DC49990A89C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"426353ee98a8d6d461a756442c152c14f38a8fc1","datavalue":{"value":{"entity-type":"item","numeric-id":5325719,"id":"Q5325719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb565e00322f2e58226ff1e046d46cf304bbf316","datavalue":{"value":{"amount":"+0.9069423675537108","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":"Q666533$84B4C07C-EF15-471E-B520-98D5F810E5B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bf88e6253a265240b655de7ded3bec309e040d3","datavalue":{"value":{"entity-type":"item","numeric-id":2962278,"id":"Q2962278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0285480ec95f3207a8fe3aaa53e3f2fecf55dd2","datavalue":{"value":{"amount":"+0.7851775884628296","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":"Q666533$D12C8BE9-987C-45F8-8FA0-9896D17D0144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86fc0d966135e7db76d89ab47cefd3aff1bd2650","datavalue":{"value":{"entity-type":"item","numeric-id":1043653,"id":"Q1043653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14741158fa2c770b3856daf6048761b93f43d5cd","datavalue":{"value":{"amount":"+0.7487642168998718","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":"Q666533$C6F4E279-B37E-4742-A012-6ADA618FBE9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b95e97e4eedcf20a982a51d35e44e6dad9e51b0","datavalue":{"value":{"entity-type":"item","numeric-id":3523085,"id":"Q3523085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84ba7ccfcb8e941911b6f587dfa8616e7c0b6145","datavalue":{"value":{"amount":"+0.7284813523292542","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":"Q666533$8F0C34B3-4E55-47A0-9317-4FED067FC9E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ca619ecf3b8d024111ba637adb3252f1d645b24","datavalue":{"value":{"entity-type":"item","numeric-id":3438926,"id":"Q3438926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"442894a561bfec3884ac76187d757616948ad2e3","datavalue":{"value":{"amount":"+0.7282305955886841","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":"Q666533$16D938C4-73FC-4C75-96AD-610205926FD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A convex relaxation bound for subgraph isomorphism","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_convex_relaxation_bound_for_subgraph_isomorphism"}}}}}