{"entities":{"Q1736617":{"pageid":1747358,"ns":120,"title":"Item:Q1736617","lastrevid":72381489,"modified":"2026-04-14T04:31:22Z","type":"item","id":"Q1736617","labels":{"en":{"language":"en","value":"Efficient algorithms for subgraph listing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042205"}},"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":"Q1736617$B7ECCF9B-DBF7-458B-ACF5-FC8D9BA5E735","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f94b6f0d59a5fffc39b53b8908012dacb37680df","datavalue":{"value":{"text":"Efficient algorithms for subgraph listing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736617$53C5FC4A-5D6B-44FC-8E9F-93BA479AC795","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fda16cd24c27cf79db73d9dff5753655ff07f746","datavalue":{"value":"1461.05224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736617$7316B5AB-75F0-495C-B4E2-0A352BE9C101","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38ab01fcb28c4a914a5a278a7666121b2e51c01c","datavalue":{"value":{"entity-type":"item","numeric-id":300257,"id":"Q300257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$86097F77-F3C9-4B80-B850-B3B87DE67F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00dfebb11dde3a8ec3e20741cb39008a3351335c","datavalue":{"value":{"entity-type":"item","numeric-id":293198,"id":"Q293198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$6C84A240-F8EC-48A9-89C5-DACDD83B5B58","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$8B06BE00-2D72-4B0F-94B6-61118626470C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736617$F527DA1C-A48A-4C93-A05C-EB9C6762123F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"889f37355db066a97fde0fe9629a9a545ef9e7aa","datavalue":{"value":"Summary: Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to \\textit{N. Chiba} and \\textit{T. Nishizeki} [SIAM J. Comput. 14, 210--223 (1985; Zbl 0572.68053)] for listing complete subgraphs of fixed size, and show that it cannot be extended to general subgraphs of fixed size. Then, we consider the algorithm due to \\textit{L. G\u0105sieniec} et al. [Inf. Process. Lett. 109, No. 4, 242--247 (2009; Zbl 1190.65073)] for finding multiple witnesses of a Boolean matrix product, and use it to design a new output-sensitive algorithm for listing all triangles in a graph. As a corollary, we obtain an output-sensitive algorithm for listing subgraphs and induced subgraphs isomorphic to an arbitrary fixed pattern graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736617$6772682A-3FC3-425E-BBEE-FA0886302BBC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736617$F85D6F06-E67B-419D-9D71-CA949EC95336","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736617$47E439A8-E457-4A0E-8978-E432F3365B16","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d1f17c5b6f9673a0abdca3b9ca43e8fcd20c722","datavalue":{"value":"7042205","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736617$7A12A8A1-5E38-43D3-92F8-260A856472E5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e87bb1aed89f5da6ee5d1aa38eb687932a17c03","datavalue":{"value":"subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736617$7BBE673C-1823-4EC3-9E19-33587106B180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e50d5f5383452bd2adcef1d921f570ccfd70e04f","datavalue":{"value":"subgraph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736617$AE2219B2-35E0-41ED-BD20-F565007B5C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"508c0becad446f9b3351fd92e6fe0f0e6f3600eb","datavalue":{"value":"subgraph listing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736617$6139481E-2261-49AC-98D6-A5647163ED64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736617$F489EA86-21E5-433E-A95D-58E63D567365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"045623e874b62da95db5174e19257fb8edebeb49","datavalue":{"value":"triangle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736617$B0DFD110-27A4-4D6E-9391-BA7BB8BBF699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58d1c451e396db63624dc61fd52bb30b0a7737d0","datavalue":{"value":"output-sensitive algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736617$610B2F2A-03B9-4C88-8A61-282D4EFB8FC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736617$3B210E86-C519-4711-829D-0B831AFB93B4","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":"Q1736617$D7697D2D-0741-489A-84FE-CCE1383BD5C9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"65b99200e9267812ddb5f260e20238935d23cdc0","datavalue":{"value":"https://doi.org/10.3390/a7020243","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736617$21B91C1A-D151-4482-ABF2-5FAF3A82F086","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0df18decc87196da047804d3fe1ea2f7489978ac","datavalue":{"value":"W1993889441","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736617$36398A7B-4990-4B8F-A9EB-22656F618928","rank":"normal"}],"P223":[{"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":"Q1736617$A1E2F5C1-75CF-474A-9F6E-C2894993DDD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54dd0e80a2032ef058a8932f0455a992b8cf4220","datavalue":{"value":{"entity-type":"item","numeric-id":3690237,"id":"Q3690237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$9CE418B5-7D0B-4254-B4A9-C2F98E382875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7af979d76b1c20fe92fb0191ce684d26e85c0463","datavalue":{"value":{"entity-type":"item","numeric-id":4167596,"id":"Q4167596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$67D3C8FD-8874-4A19-A408-A53C1B3E28B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0262c7ca9d46cfb4cf3512f2a0333529706ee62","datavalue":{"value":{"entity-type":"item","numeric-id":3684121,"id":"Q3684121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$9DECDAC6-741C-4DBA-8D1C-B38AF93708C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9531f05463941ac1635ae99ec183102ef81917f","datavalue":{"value":{"entity-type":"item","numeric-id":976085,"id":"Q976085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$19FE937C-D9E2-42E3-9ABF-2EDAC7B76AD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a533c85d71673e7ede6c73cb98ee5493ea601bf8","datavalue":{"value":{"entity-type":"item","numeric-id":3688439,"id":"Q3688439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$F68A74ED-366B-42F8-B61D-B2FB2B429833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b978fad1a53668a34ea28e884ce085a4b72b5972","datavalue":{"value":{"entity-type":"item","numeric-id":5710065,"id":"Q5710065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$F492DADA-8C82-4C4D-BE66-13F524D0C2E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"997a4e5c6e10f7b5868b2a5d332887ed8bbec1f2","datavalue":{"value":{"entity-type":"item","numeric-id":5415522,"id":"Q5415522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$E68DA6F2-65A5-4B6D-B419-478FCDF69A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"480ac560f713e57a5ee8cd072f59d2635f9c43d4","datavalue":{"value":{"entity-type":"item","numeric-id":915378,"id":"Q915378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$29FE5B83-E3FC-4072-9739-500A442A7FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11eefd7e7dc86c1755a8db4c6825e6e9fdeb6d39","datavalue":{"value":{"entity-type":"item","numeric-id":3619797,"id":"Q3619797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$11E7CF71-7888-4B7F-929A-4C8CC3D5B5F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5a591c7a666105bc0d8041074a34a42050aeafc","datavalue":{"value":{"entity-type":"item","numeric-id":2842169,"id":"Q2842169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$0D892FC5-6023-43E4-AD7F-E9664AE5AB2E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"38375c767bf5a4ae0104b8b4a945e3e50f6c8778","datavalue":{"value":"10.3390/A7020243","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736617$29CB6FF0-0709-4DB7-8EA7-2842C87FC715","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db001beffa45c8c9471a6db9982520989160bd96","datavalue":{"value":{"entity-type":"item","numeric-id":439930,"id":"Q439930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62aab4df19bef4d1cb879465e2ebd17884f1b1d7","datavalue":{"value":{"amount":"+0.8002692461013794","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":"Q1736617$A934BBC9-694D-42B7-978A-3CB2B7C60B96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"106f51c0921fc7bc167579760de1a27d9e72b625","datavalue":{"value":{"entity-type":"item","numeric-id":3690237,"id":"Q3690237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6771d1076172aae22393bbb455972dded3830190","datavalue":{"value":{"amount":"+0.7913573980331421","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":"Q1736617$1285DD3D-46B7-402C-83DB-BEDF185784B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"873c8e437a6565240518654b3a8f0202af7cea88","datavalue":{"value":{"entity-type":"item","numeric-id":5502097,"id":"Q5502097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dc5bb999af84e2a3359d7d345ad152729e67c90","datavalue":{"value":{"amount":"+0.7886350750923157","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":"Q1736617$37BAD3C6-4F47-4026-BF67-87B44BA6405F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24dac847cfc328d99e745e73ce9bbf34283fc81b","datavalue":{"value":{"entity-type":"item","numeric-id":2872118,"id":"Q2872118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2d7e84f099f6d6177100cb925622291ef36a72a","datavalue":{"value":{"amount":"+0.7871477603912354","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":"Q1736617$CEE624CF-FD35-4E30-8030-E799E6845DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"472d68c41fd40c79470aff09654eaa472870fefe","datavalue":{"value":{"entity-type":"item","numeric-id":4861348,"id":"Q4861348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f3a0881b72f80a3f6e59e1db562d0d9fd490313","datavalue":{"value":{"amount":"+0.7755986452102661","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":"Q1736617$A57120FB-F882-4076-A600-DF41C5B5AE63","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736617$E0C9CEF1-BBC4-4CE2-BCE1-6357BDF98481","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient algorithms for subgraph listing","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_algorithms_for_subgraph_listing"}}}}}