{"entities":{"Q2045031":{"pageid":2055773,"ns":120,"title":"Item:Q2045031","lastrevid":72507408,"modified":"2026-04-14T05:23:45Z","type":"item","id":"Q2045031","labels":{"en":{"language":"en","value":"Complete-subgraph-transversal-sets problem on bounded treewidth graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7380949"}},"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":"Q2045031$29F59033-5F87-443B-AF02-D7E26599AEC6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"365d647b9db32964a8d002d5f393b7f8dbd0fdd5","datavalue":{"value":{"text":"Complete-subgraph-transversal-sets problem on bounded treewidth graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2045031$D051D450-C7DD-449C-AD41-486506DC1346","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f850285354f7a44318d48a38eb9e84f7e3fbd9b","datavalue":{"value":{"entity-type":"item","numeric-id":216200,"id":"Q216200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$A780704B-1819-4C3A-96DB-E02A3656740E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fd14e45d53468c8010c651737c73736a189c385","datavalue":{"value":{"entity-type":"item","numeric-id":221708,"id":"Q221708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$CA378BF5-881C-40E8-AB4D-EB7E70F5B9F2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dcf8815e3b257674fa147da7a4e7c92c91c0b3e3","datavalue":{"value":{"entity-type":"item","numeric-id":185429,"id":"Q185429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$31AB6E2B-B2F5-43E8-B2B8-9B1E18D5871B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8eff5628bfe7613d74059f776f508bd7d2f0889c","datavalue":{"value":{"time":"+2021-08-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2045031$6FCF38E0-EBCD-4B71-B215-66199ECD1DBE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4d5473fea13f6cbff8ecf02746248c6fb440ba32","datavalue":{"value":"The paper considers the Complete-Subgraph-Transversal-Set problem and the \\(L\\)-Max Complete-Subgraph-Transversal-Set problem. Polynomial time algorithms are presented for the two problems on graphs of bounded treewidth. The authors show the connections between these two problems with some other known NP-complete problems such as the Clique-Transversal-Set problem on graphs and the Vertex-Cover problem on hypergraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2045031$AE5B186C-A327-43D1-9FE8-51B7F0D0C431","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045031$8B965232-7F47-4CCF-A78E-1C564769CD44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a58528c037ed952fc79e3e7fc7617f0a0e25ff15","datavalue":{"value":"7380949","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045031$077B8A67-1DF6-4FD0-9A40-10DE32317507","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q2045031$CF08AEA0-6C6A-4C9B-BB49-400EE359E4C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4476577ef0f7476e08816937ecb9cf3e4fa07295","datavalue":{"value":"complete subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2045031$E0AF7B11-E8E4-4B99-80C1-7CDAB00758DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2045031$E0F8B4D8-4894-46C6-BA83-E63940348D40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2045031$6B4E9003-792B-4C7F-9B67-4F9D61617140","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":"Q2045031$5293AD21-212C-45B9-9F64-711AB103CF5D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4220a647b479b27476047ba38a1c03cba8611de2","datavalue":{"value":"https://doi.org/10.1007/s10878-021-00703-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q2045031$9CB22956-FF35-419B-886E-55951110BFBD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"54834f07f54ea078e9f9c9e7a99725b0e6ca21e4","datavalue":{"value":"W3161063901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045031$02242043-415D-49AF-90F9-D69EFE84DDE0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bf3b594d0086b2ca7a669f4b34a72b12bbd1393","datavalue":{"value":{"entity-type":"item","numeric-id":1849745,"id":"Q1849745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$FB39B5DD-249A-4438-92BE-0B63895FBC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"770bb68de47752f527df3eb5fd0239815f0bd638","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$AC3572C2-12D0-434B-931A-002CA149D77C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"678e7a4be408fd6129f52f04fe687f74c25ca083","datavalue":{"value":{"entity-type":"item","numeric-id":2554881,"id":"Q2554881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$62194582-21DF-4324-9739-B1A352BF52C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747a911f10480a7188a201d8808620458b2a3690","datavalue":{"value":{"entity-type":"item","numeric-id":5691297,"id":"Q5691297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$5F426BC3-E2C1-43DB-BC9C-163E05BB484B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d6dbc209049894a0a69c9c432cfaff9eadf5de4","datavalue":{"value":{"entity-type":"item","numeric-id":2583124,"id":"Q2583124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$730FC818-E109-4000-A570-D66589280158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4209ec833bbee0f3e68747612bfa0bf13e08d4b5","datavalue":{"value":{"entity-type":"item","numeric-id":5285934,"id":"Q5285934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$3985566D-0462-4365-B400-4750AAEFBA60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2797d7af87aa7473769c0ba5e3f8de0b7a15e7f2","datavalue":{"value":{"entity-type":"item","numeric-id":1917287,"id":"Q1917287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$71E7631A-F712-4733-957B-02CCC03656DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5890ae5a283b4e8716396304a346cee90071e82","datavalue":{"value":{"entity-type":"item","numeric-id":1854773,"id":"Q1854773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$522D9D21-5BD1-403E-8D4F-FB49D140A32A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70c937326045597237bc5e22805f0b091613787c","datavalue":{"value":{"entity-type":"item","numeric-id":1201260,"id":"Q1201260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$AFDEAF29-66C0-49C7-B34C-53A61C1491C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d396299693e4f28921602182db43542ab4b6d60","datavalue":{"value":{"entity-type":"item","numeric-id":2519023,"id":"Q2519023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$670E079D-044F-443C-BB98-3AC708CF2641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d8c3c9a4b968f607553357d3b0f2f035ae1da1d","datavalue":{"value":{"entity-type":"item","numeric-id":1971220,"id":"Q1971220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$6911D29A-E66B-4115-BC81-681FB112FBE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cd64e41383e58b27038dda2995ea96c06c46af4","datavalue":{"value":{"entity-type":"item","numeric-id":1230790,"id":"Q1230790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$0496BE33-2980-473A-AC8D-2AC43B4169F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85859d4bf1a3e88a94a43f3e1ce8b0cfd1f2c77b","datavalue":{"value":{"entity-type":"item","numeric-id":3002852,"id":"Q3002852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$1696124B-7E9A-4C60-B004-E48EBF11F365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55bdf4ec7260080ec2ace85e7db971d84eebc13f","datavalue":{"value":{"entity-type":"item","numeric-id":1801672,"id":"Q1801672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$1F984886-7A57-499C-93B3-92FA494D6265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99f46437df2a7df52d651d2a340eb13ade27a691","datavalue":{"value":{"entity-type":"item","numeric-id":2489948,"id":"Q2489948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$A8130E98-FEBE-4845-B9DC-2E704D979A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9388c609ecf8867480347b0a90486d5114fe230d","datavalue":{"value":{"entity-type":"item","numeric-id":1944214,"id":"Q1944214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$E0934CDC-578F-44E1-B3DA-99698A90728D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1357b15aa0895d858d392a7ff419092326aafa","datavalue":{"value":{"entity-type":"item","numeric-id":5710169,"id":"Q5710169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$33CDECFA-3D52-43D2-B577-9F4435EDC68D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e5eb92b8bc8a686032a52d19f05936859c53c10","datavalue":{"value":{"entity-type":"item","numeric-id":1779691,"id":"Q1779691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$BD3CDBEB-AF27-4C39-84C2-A01C2F07528E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ef0f89b3d4848285d16b9f024f89d4a5e76a218","datavalue":{"value":{"entity-type":"item","numeric-id":799684,"id":"Q799684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$A335E912-22E1-4EF9-A6A8-FC432E636F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00b79ce7beb3596052714e5eb40fbfabb9a3ecac","datavalue":{"value":{"entity-type":"item","numeric-id":1174130,"id":"Q1174130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$BD753145-8930-44FB-8B3B-182B6181B4CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8658e6d71d7258b809c478c332d93b25a4d9b43","datavalue":{"value":{"entity-type":"item","numeric-id":4782696,"id":"Q4782696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045031$90638ECB-00B1-454C-A25C-0233DD2A0100","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b174416912d43f1517b3eb602f3743a3fd0480ee","datavalue":{"value":"10.1007/S10878-021-00703-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045031$675E26F8-0F35-49F3-80B1-C6AAD2C85B33","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d51bcedbddd193fa414d6e14771039b2435f2b64","datavalue":{"value":{"entity-type":"item","numeric-id":3795218,"id":"Q3795218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ef615a526f50843fda1c61284c60cbbcb61b564","datavalue":{"value":{"amount":"+0.7824233174324036","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":"Q2045031$2685386B-CCDC-43D1-8025-A5114BF4C903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f0281769d61d46b1f59be8c8d861ff0e38213c4","datavalue":{"value":{"entity-type":"item","numeric-id":5150424,"id":"Q5150424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e370fa914fa8c73bcdbe6418d0d2616a251afb8","datavalue":{"value":{"amount":"+0.777612030506134","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":"Q2045031$6F2F51DC-2B0E-4A2F-8446-24FF9A686D2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4acc1b8b067556a7a37bcfb21ea1f141650453af","datavalue":{"value":{"entity-type":"item","numeric-id":4554340,"id":"Q4554340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b5860bf61da2281835a8e407fce376db8adc14f","datavalue":{"value":{"amount":"+0.7666671276092529","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":"Q2045031$6767F00B-C689-4BB9-8B9B-E8B01DC7A56C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bfc2f0543877e042a766dac970cb0a0fa20bc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5150500,"id":"Q5150500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"604effc4d2aebffe36f5690e7048cacb1514a338","datavalue":{"value":{"amount":"+0.7661048173904419","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":"Q2045031$4347471E-F174-4894-9EE7-5635E6E17EEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"818a858dad2b8a74d0f9a54dd9459beb1fba1589","datavalue":{"value":{"entity-type":"item","numeric-id":5365080,"id":"Q5365080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d583068213e3db69f1d78a50049409afdc45fd2f","datavalue":{"value":{"amount":"+0.7632668614387512","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":"Q2045031$50FFA6BA-C9EF-4B77-88CB-9F37B563D663","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complete-subgraph-transversal-sets problem on bounded treewidth graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complete-subgraph-transversal-sets_problem_on_bounded_treewidth_graphs"}}}}}