{"entities":{"Q1736548":{"pageid":1747289,"ns":120,"title":"Item:Q1736548","lastrevid":72377601,"modified":"2026-04-14T04:29:54Z","type":"item","id":"Q1736548","labels":{"en":{"language":"en","value":"A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042154"}},"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":"Q1736548$360012EA-EF81-4177-9DCD-78BB7DCDBCC2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fda135fbf9b3b146b417829f0a037cbcff683ca3","datavalue":{"value":{"text":"A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736548$AE23E91E-9614-4565-9AD8-E7C99B3C54E9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47a4c4016b63b22a188b5740f2ac3d7c8bf8d2a0","datavalue":{"value":"1461.68140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736548$DD65A57F-9464-4511-9E91-ED220FB9604F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bef97d591ff4cff143a337bfbd4d41c37042e229","datavalue":{"value":{"entity-type":"item","numeric-id":407557,"id":"Q407557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$252F1C65-BCB8-4F77-B3ED-0371234E8722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2d9d005e6fe7a76918135372ac64c00ca2bccd6","datavalue":{"value":{"entity-type":"item","numeric-id":620948,"id":"Q620948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$28C3C535-8832-468C-A8B8-F8D9F3C3FF59","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":"Q1736548$78AB0D88-63C2-4D73-83E8-1917D22D1E2D","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":"Q1736548$89936D85-4781-4F8D-9611-D45C14F26835","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab954e207b2e78ee47b76776a96e89ac978094ab","datavalue":{"value":"Summary: The maximum common connected edge subgraph problem is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs, where it has applications in pattern recognition and chemistry. This paper presents a dynamic programming algorithm for the problem when the two input graphs are outerplanar graphs of a bounded vertex degree, where it is known that the problem is NP-hard, even for outerplanar graphs of an unbounded degree. Although the algorithm repeatedly modifies input graphs, it is shown that the number of relevant subproblems is polynomially bounded, and thus, the algorithm works in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736548$BADF9531-398F-4B15-8437-4ADBD163E3BE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736548$ACF33744-402D-41B6-90AB-45DC71C0B65D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736548$CE830783-AF94-4F21-9F93-66A4239B20B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736548$0FBDB836-0D54-47BB-806F-960583861D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736548$5A659CC1-F53B-4A37-9180-B7A4448FBD7E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4baa50336e6f553bd7d70e00f8cdebd85a1033ce","datavalue":{"value":"7042154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736548$A2D0FF90-E0D0-45CF-933F-567A5FBE97B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb1d35a2ecf73f0130b2a5d33ef40972a27b961d","datavalue":{"value":"maximum common subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736548$E600B210-A528-40D2-83AD-51CB921DE1C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3801589e3f1cac737b9dede93572ceb157c30bc4","datavalue":{"value":"outerplanar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736548$2EA57BC0-DEEC-4D8D-A05D-3C349F3DC420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736548$C06F4FA8-D6F9-44A9-87F9-7B0B7E87325F","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":"Q1736548$0423A544-9B6D-4533-B027-DC2E3968EAB5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c99c59096e81add0567bc4557c4b9d507a7eeec1","datavalue":{"value":"https://doi.org/10.3390/a6010119","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736548$86EA1A99-7E0F-4AC1-AED5-C48E49AF61D5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"22de02069072e7e2d083dbe1d8138ed2f2d464f9","datavalue":{"value":"W2046820662","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736548$41761993-D38C-404E-AF03-9972628B2A31","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"380b9f0e14f4995b59aba49080115febbd57d3a3","datavalue":{"value":"Q115926164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736548$D1725FB1-3637-4EA9-81D2-54F1608F0288","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"815dfe98020b311e9b907b7bff2c2c22442d8842","datavalue":{"value":{"entity-type":"item","numeric-id":1860118,"id":"Q1860118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$65E5D0B7-E789-4457-A758-9D1206F4C222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b77678c9d65bb757616e12f06330c33356f9940","datavalue":{"value":{"entity-type":"item","numeric-id":5096796,"id":"Q5096796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$1AD85938-738C-4DB0-8EB6-159831E19CFA","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":"Q1736548$C1D2D66E-0CE7-4C58-ACD1-9311B958CDF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31c128c6d0786632d741af42236e7d5e8f0768aa","datavalue":{"value":{"entity-type":"item","numeric-id":834895,"id":"Q834895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$35C1DCF1-B88B-476E-90D2-E85CB7B8E40D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f354148bb2298c19b16334afb7165400143221b5","datavalue":{"value":{"entity-type":"item","numeric-id":2248525,"id":"Q2248525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$4CB138C3-FE41-458C-A485-12254B7ECB4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"244b9799b6426900ac723edc045fb74206368829","datavalue":{"value":{"entity-type":"item","numeric-id":3378496,"id":"Q3378496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$6F79C306-CD96-45B6-9140-00A08901BC61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b1f8dacc5aa90cea438e987291a95980f58b616","datavalue":{"value":{"entity-type":"item","numeric-id":1823708,"id":"Q1823708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$42713133-AE4D-44EF-9479-3B1F84D70940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b50bad9b5e66b2da9e23a06d8d2e993a52d5f6b","datavalue":{"value":{"entity-type":"item","numeric-id":1056237,"id":"Q1056237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$E9AB9888-27C6-481F-BA39-1EA828D1BF1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb4cf073b41de29a3d21883982f338b2e7b37cc0","datavalue":{"value":{"entity-type":"item","numeric-id":1578418,"id":"Q1578418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$16B762FB-074D-4591-88E6-BBC91D3BA5FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06fc5de190fb004abdb8926e0e546be8f22fbd06","datavalue":{"value":{"entity-type":"item","numeric-id":881594,"id":"Q881594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$DED78160-308E-4CC5-A845-89A559AE39BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1401f0e3b38bf7b5fd23d8c6b049aa95081e464d","datavalue":{"value":{"entity-type":"item","numeric-id":2912710,"id":"Q2912710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$1BB0854E-9BEA-4EEA-B288-FD3E9084D674","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4602778c2c6575754b2c5dadce1ffe3ea7ab7c10","datavalue":{"value":{"entity-type":"item","numeric-id":1255015,"id":"Q1255015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$F654A1BE-107C-4E93-98F4-7C393DD69A1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0366292b0789d80a51665a228d256459b0d865c9","datavalue":{"value":{"entity-type":"item","numeric-id":3451017,"id":"Q3451017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$89B75D6F-8882-4475-9949-C4E582F8A892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9194e9b150f8488fef979658da21ddd0e60751fc","datavalue":{"value":{"entity-type":"item","numeric-id":3651735,"id":"Q3651735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$A7160F0F-E736-4BDB-B58A-BF358B4E7967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c5b2685bd653be07358dc8c27bf61344b25578a","datavalue":{"value":{"entity-type":"item","numeric-id":4909531,"id":"Q4909531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736548$66329F00-B96B-4179-ADC8-16383AB26058","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2e7584959b46e40bf08169c57c95fff66d114aef","datavalue":{"value":"10.3390/A6010119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736548$0AEDA272-14C9-47E1-89E2-219B7F2C8342","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43b713f1f10cb9ac162a93e04f8b8e10f9f9e616","datavalue":{"value":{"entity-type":"item","numeric-id":2912710,"id":"Q2912710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fa9b5d90d38094b7771110ba46d6f9974e4867f","datavalue":{"value":{"amount":"+0.9473132491111756","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":"Q1736548$5985855F-9BEB-4748-932E-803B79D50C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f44a091d2633faa9f88936da859ff3f41a4ac86","datavalue":{"value":{"entity-type":"item","numeric-id":5191633,"id":"Q5191633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"800bcf2299881e8dad941f3ddaf4b0669f797685","datavalue":{"value":{"amount":"+0.838760495185852","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":"Q1736548$31F4F988-DE8E-42B6-B425-64660F5B2D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d987e726f29da6a45c4181d0c0e71c509cdddd9f","datavalue":{"value":{"entity-type":"item","numeric-id":1678090,"id":"Q1678090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d3e6cb0c9fb9a2066aab061c50f54355061bcae","datavalue":{"value":{"amount":"+0.8346174359321594","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":"Q1736548$51145A58-BD30-4553-91D0-0D7062058D18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f094116a7622d45d02520edafc8562ec073ddb3","datavalue":{"value":{"entity-type":"item","numeric-id":4909531,"id":"Q4909531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"635625e69d7f0e1741b84657cadeb3d7c50c5d43","datavalue":{"value":{"amount":"+0.8321755528450012","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":"Q1736548$EAEC1A7D-BB8A-4D29-9168-89F4CB782B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d94b217b688700d8ccc10521849d0e61bf15fa21","datavalue":{"value":{"entity-type":"item","numeric-id":2946055,"id":"Q2946055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17bf3265eabad3134aba3e25a872c33664831698","datavalue":{"value":{"amount":"+0.8313836455345154","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":"Q1736548$02999E7C-A9DE-44D4-88F1-F78C9BF6EB85","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":"Q1736548$AD949AEE-03FA-4F77-A4DE-F6E2E6EA1A1B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial-time_algorithm_for_computing_the_maximum_common_connected_edge_subgraph_of_outerplanar_graphs_of_bounded_degree"}}}}}