{"entities":{"Q1589412":{"pageid":1600152,"ns":120,"title":"Item:Q1589412","lastrevid":47546263,"modified":"2026-01-02T01:16:19Z","type":"item","id":"Q1589412","labels":{"en":{"language":"en","value":"Enumerating all connected maximal common subgraphs in two graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1542255"}},"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":"Q1589412$31FA2708-8949-4817-BF1F-DF7919771A68","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0eec691681a018011c1c09b1b15d4443a68642dd","datavalue":{"value":{"text":"Enumerating all connected maximal common subgraphs in two graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1589412$8433F7D8-A68A-4EF4-ACF1-423486EE996E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ae4944ac6e848b63ceea1e884a121bc0c272d2d","datavalue":{"value":"0952.68105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589412$A2422DAC-A291-4E36-8486-1B2CCC94C577","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0ad9af73c3565fd596bd5fc551c0f686d0870005","datavalue":{"value":"10.1016/S0304-3975(00)00286-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589412$02BDE38B-4DEE-416A-A69F-54CE4FB4AB8C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ca85145c5bcf26b9d6b48940983710606ab54cb","datavalue":{"value":{"entity-type":"item","numeric-id":1581051,"id":"Q1581051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$0930E1BF-2E1A-4450-9398-9D4EC9CBDC4B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$B159B408-73BA-4E98-9B4D-263D138FAF14","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fc98fd02909f39fc4d6749553781a25cceed046","datavalue":{"value":{"time":"+2000-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1589412$B5A6A5CF-2E64-4CC2-A68E-AC3417AF6DC7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4ac96df448185da456a8d9cc625c24600324ff5b","datavalue":{"value":"We represent a new method for finding all connected maximal common subgraphs in two graphs which is based on the transformation of the problem into the clique problem. We have developed new algorithms for enumerating all cliques that represent connected maximal common subgraphs. These algorithms are based on variants of the Bron-Kerbosch algorithm. In this paper we explain the transformation of the maximal common subgraph problem into the clique problem. We give a short summary of the variants of the Bron-Kerbosch algorithm in order to explain the modification of that algorithm such that the detected cliques represent connected maximal common subgraphs. After introducing and proving several variants of the modified algorithm we discuss the runtimes for all variants by means of random graphs. The results show the drastical reduction of the runtimes for the new algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589412$0DF98752-88D2-4203-9230-250ABF3D2E40","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589412$26DF0B95-4B7B-4797-94EF-49E0DC3886C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"285a670b12d59f52a2c22aff159f96fb531e0298","datavalue":{"value":"1542255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589412$07BC6548-5107-48B8-BDA0-40C94D4A1562","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589412$37505370-87CA-48A4-897B-55D6393C0B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04c93c354a7c987fb13626659153d0515f50827c","datavalue":{"value":"connected maximal common subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589412$B7963C43-1119-4898-B99E-880822803494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589412$6332F084-73FE-4C50-AF4C-888AAAA14DB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c81a3b079895a56bc7a6c3014e8646c7c358102d","datavalue":{"value":"Bron-Kerbosch algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589412$B5344967-38B4-4AAE-9BC8-1E67CB2A91C9","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"0bd02c26dee295e17fa1661a740b0e3277993f7d","datavalue":{"value":{"entity-type":"item","numeric-id":37543,"id":"Q37543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$FC6AC163-000B-42DA-9998-2306E69235DD","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":"Q1589412$8BF3A01E-D932-4719-A4FC-B41C733F7012","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6de0c79823e6538f827923bf16768c83c28b903c","datavalue":{"value":{"entity-type":"item","numeric-id":5650710,"id":"Q5650710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$58343D07-2AEE-446E-84E5-0EB2712AAA53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d633291d3e7be6bc798ce06a78bf99c246cd5783","datavalue":{"value":{"entity-type":"item","numeric-id":5899820,"id":"Q5899820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$21682F4F-BE67-4C4A-8302-8529034BCEC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d1749a981950e54d9bd51c59ee6965d1349b296","datavalue":{"value":{"entity-type":"item","numeric-id":4161101,"id":"Q4161101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$F676E7C5-50D8-4589-A35A-BEEAF1EC51C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63b5b04ed3aa0acdcae036286ca8192fe935fcbb","datavalue":{"value":{"entity-type":"item","numeric-id":3741641,"id":"Q3741641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$0E371BE5-5F72-4396-BEDA-276C77F8CC79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"078e0a5ec559210a14a4145be98e18a1a255f6b1","datavalue":{"value":{"entity-type":"item","numeric-id":5677064,"id":"Q5677064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$63E3C352-C014-4AA9-B9DB-939FDC8A7B78","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":"Q1589412$C8B1D48A-36C1-4859-BD87-D86E2BE8D22F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33959e8c3fbe7080f98305389592daf8f06321e","datavalue":{"value":{"entity-type":"item","numeric-id":5634016,"id":"Q5634016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$C30BBA33-990F-4F0F-AF4E-92E2BEE4D417","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10af3f4734cb511b3f08e84af924b8516b337a81","datavalue":{"value":{"entity-type":"item","numeric-id":1143177,"id":"Q1143177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$EE8F276D-16E4-4BAF-8997-5F27D0D5F73D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$8ADB9EC6-BE1B-4377-A25D-A1ABA22F1C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e232f897f83995c91a8f2ae4f45067793634701a","datavalue":{"value":{"entity-type":"item","numeric-id":4770974,"id":"Q4770974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$79DB9BF5-5086-4B96-A1D8-EDD50C162471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4430547256196434a5fcb8ecc7f9eb44d98ed973","datavalue":{"value":{"entity-type":"item","numeric-id":3899836,"id":"Q3899836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$7F81DD29-1A2A-4540-8FFE-44E406D2BCB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54031fdf5e090404b1eee09e831fb3b4d0991ad1","datavalue":{"value":{"entity-type":"item","numeric-id":4185818,"id":"Q4185818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$88770CC8-5E86-4FA6-AE86-65E9E2B8B3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e01e3ca7c8e2ea268be87eb72edacec3b8cad6bb","datavalue":{"value":{"entity-type":"item","numeric-id":2560433,"id":"Q2560433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$94AE856D-DF68-46CC-B5CE-3F1B88F7A609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65c334f24f0ea0f5930a0f10f3816e5cbac17eea","datavalue":{"value":{"entity-type":"item","numeric-id":5920767,"id":"Q5920767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$4810163E-44A9-4CC4-9553-4B45C913C9B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a474d23d513d51ae373e40119bedd788252f2a8","datavalue":{"value":{"entity-type":"item","numeric-id":3812281,"id":"Q3812281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$40EBB454-0138-4CAB-8D0D-48E4CABA9AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dc8a1faedec1647ff5e9aefae185cf306f2bc5","datavalue":{"value":{"entity-type":"item","numeric-id":4133117,"id":"Q4133117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589412$C9FCFCD2-A9D7-4A50-9292-AA65B0FA0E98","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"38bd50afaaf80830b367db43e6625f9544c45216","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(00)00286-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1589412$F608DA1A-0397-40CC-BF73-5CBBD0585F51","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8b613bdb4037198e2bf0dedeff28c200b67b0c7b","datavalue":{"value":"W2051658231","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589412$4FD77236-CA60-4726-9D12-547E83675D0F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b928faac67f7fe558e10848947e5746a2e0920a","datavalue":{"value":{"entity-type":"item","numeric-id":1790989,"id":"Q1790989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"636103a03320ce30be40eecf0eeff4c6c35cb470","datavalue":{"value":{"amount":"+0.818986713886261","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":"Q1589412$5C61686E-42BC-4E38-B9B1-7BB0225C0F65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2234c276cde995dcf1c9260ab75aa0665161017","datavalue":{"value":{"entity-type":"item","numeric-id":5716994,"id":"Q5716994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cdb9b443e75137c4bcba8d63d0f6974f7a352f3","datavalue":{"value":{"amount":"+0.8124422430992126","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":"Q1589412$219FAF56-4FAD-49AC-A1F0-E189A0B186F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62ce05e3ed2d70ce2bb86db97b14806fb50ee5ac","datavalue":{"value":{"entity-type":"item","numeric-id":5316453,"id":"Q5316453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6282cf061d3a9fab47f9124637e4a1355694e3a4","datavalue":{"value":{"amount":"+0.8084908723831177","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":"Q1589412$21F350D5-4407-4E62-A04E-12A82A1ED2F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8609fe4b4c2b8e88bfe6c181a91ee9c533dbaa5c","datavalue":{"value":{"entity-type":"item","numeric-id":3627718,"id":"Q3627718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"936e148e79399fb724ab0ff253c583463253659c","datavalue":{"value":{"amount":"+0.8065043091773987","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":"Q1589412$6D1F75E7-09EE-4467-84C4-FB6889B47070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21e9156a6b64eaed5b25004f66b9b31627cf3a03","datavalue":{"value":{"entity-type":"item","numeric-id":4808935,"id":"Q4808935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8a6fefd419483f231d5081972a60076a9829c4d","datavalue":{"value":{"amount":"+0.7980066537857056","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":"Q1589412$24209B3C-3C7D-404E-84E0-A20D55136185","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1589412","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1589412"}}}}}