{"entities":{"Q2041983":{"pageid":2052725,"ns":120,"title":"Item:Q2041983","lastrevid":54050720,"modified":"2026-01-26T04:05:00Z","type":"item","id":"Q2041983","labels":{"en":{"language":"en","value":"Beating treewidth for average-case subgraph isomorphism"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7374882"}},"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":"Q2041983$66AD631A-4B0B-4387-8EAD-EE39950940CD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"80070399f54b9477cb103b8b89d8daf9a84e5752","datavalue":{"value":{"text":"Beating treewidth for average-case subgraph isomorphism","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2041983$86F079FF-ED8D-4352-8619-AD7F9FB99B81","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a86fae247a3bcef927f70ac4ea6b064cdb94a6a7","datavalue":{"value":{"entity-type":"item","numeric-id":2041982,"id":"Q2041982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$0AA60EC0-AD6F-49FC-BA09-3660255FB413","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$AACCD82F-51E5-4AE6-ADEE-A5F0113B8E0D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"837bc3912e68c80895b26e4dcc78c9f39b1564e0","datavalue":{"value":{"time":"+2021-07-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":"Q2041983$A12AF384-DED3-487B-AA42-A5774DE2123E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"824c34fbe0717ee8c84bdcd80d7c3c10539bf257","datavalue":{"value":"https://arxiv.org/abs/1902.06380","type":"string"},"datatype":"url"},"type":"statement","id":"Q2041983$D07D641E-8217-4894-8B29-8F8650F2B50C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"019e34575925d0f68ce73f35cbf28200681d654f","datavalue":{"value":"https://drops.dagstuhl.de/opus/volltexte/2019/11485/","type":"string"},"datatype":"url"},"type":"statement","id":"Q2041983$E43B2823-AE35-4686-80E1-FE3BC64CC21A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa684c8d52e9da1094b0c2d762898ace723c7ee3","datavalue":{"value":"68Wxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2041983$8F2B23FA-A165-41AC-9309-A37C3E1E0FA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f1a97a7188d4143e338e99eba7d65493911702cf","datavalue":{"value":"05Cxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2041983$53D31AED-28CC-4DEF-B260-AE1C1CFE7602","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2f993cd4ca2e705b1dba94703353709b63bdd1a5","datavalue":{"value":"7374882","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2041983$B5B44C88-4085-40F1-81E4-9D9429F8C5FA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e50d5f5383452bd2adcef1d921f570ccfd70e04f","datavalue":{"value":"subgraph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q2041983$0EA4609A-C316-4859-8C53-F76F19461B99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeb5cf5222b6371fb7f9c168c78eb205663c9be7","datavalue":{"value":"average-case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2041983$2165F41F-6D31-41CE-8DB1-D33C8A7B4F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b566b19bacfd137ad26b1a567ce68ab860631fa","datavalue":{"value":"\\(\\mathrm{AC}^0\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q2041983$4559EC65-EAE6-4F51-9A56-2527E1CB41E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2041983$6808DE38-4527-4DD6-9920-DB1FC44C3703","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":"Q2041983$ECF245A8-792D-42CD-A923-09472B161AE9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"27fc9418f20f29f8abf0bcbc5e4952e349612ac2","datavalue":{"value":"W2997589087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2041983$3E3C5AA1-0CEA-4487-BB33-DC53D4223ABF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"99725c8075de63c7bd6b763d57e2592f23449e8e","datavalue":{"value":{"entity-type":"item","numeric-id":3094934,"id":"Q3094934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$5D07FA8C-55EA-4982-80EE-3A0C2D36C5CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0df8c16fb6d4d3c861f57e0569695f268c7efadd","datavalue":{"value":{"entity-type":"item","numeric-id":800384,"id":"Q800384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$6283705B-2364-4C1A-8CF3-C1DBCC565501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42451d9b2f091244b010a7dc1fc6a0f53a57abc4","datavalue":{"value":{"entity-type":"item","numeric-id":4369883,"id":"Q4369883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$4D72A64B-C176-4AC6-B71C-243C5381C800","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a774b6029c9da3ff517fc7d194393fbcab2285b","datavalue":{"value":{"entity-type":"item","numeric-id":626676,"id":"Q626676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$2331D402-392F-4F8A-B65F-A327BC655688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57515aea1ad564d767f2a1d2b4fdb04b8bf50ff4","datavalue":{"value":{"entity-type":"item","numeric-id":1274912,"id":"Q1274912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$ABF5F4A8-D0C8-4AAC-BB9E-054062EB1E5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e115af69c1d72ad51c792390a5a1864f01b239fd","datavalue":{"value":{"entity-type":"item","numeric-id":819827,"id":"Q819827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$920B35B8-925C-481D-B427-393A15338977","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"709824e9bd3f1645aede079612275dfec52dc319","datavalue":{"value":{"entity-type":"item","numeric-id":703534,"id":"Q703534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$6F3C70FD-A6A0-458D-B02D-1780F27BF792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5174ef1552dc71573cbf33fdee850446520d2d75","datavalue":{"value":{"entity-type":"item","numeric-id":1302164,"id":"Q1302164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$1681B73A-22DE-4794-9259-679DF0D0F706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d51d2427facdc42ce1e84dc05815c9d772dbbe37","datavalue":{"value":{"entity-type":"item","numeric-id":4458414,"id":"Q4458414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$76BA548E-67B8-4A10-A239-05D76BB534CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5dc42a680b8ef6292b67bd3175f40575a5cbf46","datavalue":{"value":{"entity-type":"item","numeric-id":2978180,"id":"Q2978180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$1AD0709A-5B6A-46EC-B5E8-3C359F7511C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"415bf483704832dfb1db3c30f31c6afc6a0cd336","datavalue":{"value":{"entity-type":"item","numeric-id":1322486,"id":"Q1322486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$C7A738DB-2E03-459B-A454-B1AF672BB6A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca4be033dc1e037b43c1538205386964bc6ef38a","datavalue":{"value":{"entity-type":"item","numeric-id":3514498,"id":"Q3514498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$F3782F82-0C6D-44B2-8133-697511CF0DB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4548ea5d583917c0fa9b6aaa6b1d48c80c1e7e","datavalue":{"value":{"entity-type":"item","numeric-id":1604206,"id":"Q1604206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$C75354E7-1191-44D9-AD4A-C60216B936C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcc85ab9fa16bca6fc418f173746a68af16e1d0b","datavalue":{"value":{"entity-type":"item","numeric-id":3977078,"id":"Q3977078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$3DB5AB54-274F-4B9C-A7A7-9E511C04D1A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93a5515faf63239f08c6b84830cd3e904bed3a6c","datavalue":{"value":{"entity-type":"item","numeric-id":5737815,"id":"Q5737815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$6B3C1A5F-4A9A-4C1F-92FB-99AA68D16628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bba75b1fcf7bdfc096d3519487d870ba27bfb198","datavalue":{"value":{"entity-type":"item","numeric-id":3002818,"id":"Q3002818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$05568E58-F38A-49D7-B1F3-C4D906246B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"816958e4557d45e7d4a014a4eb6b7111e4cc97ac","datavalue":{"value":{"entity-type":"item","numeric-id":2965515,"id":"Q2965515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$5F321CAF-3EA5-4FC9-9CDA-A487E80696FA","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":"Q2041983$5F28FC6F-9E60-48CB-91C6-F52DB2D523DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6760c1a0ed84f473ebf9c19dbb4d05bbf42b9a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3751592,"id":"Q3751592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$E69E288B-9455-4038-8418-7C93A399CE55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"422191f7fa8b2d64e6ff41dbfa56ea42d38984ad","datavalue":{"value":{"entity-type":"item","numeric-id":5302097,"id":"Q5302097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$4FE0F681-B329-4E62-9B67-852C0329C517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e66a110865835c12e1e9ee90366a1cba06155f5","datavalue":{"value":{"entity-type":"item","numeric-id":5419039,"id":"Q5419039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$6B096B68-6BC5-4C1C-89C4-EDA8F8A06980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a46902c26a9d2ad42ac08508d42315cef394f156","datavalue":{"value":{"entity-type":"item","numeric-id":5122162,"id":"Q5122162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$B34F1E25-8527-44AC-857E-4D80873EEF4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e28415c2fdc9cf4fbb4ddf313db6e38750a0880f","datavalue":{"value":{"entity-type":"item","numeric-id":4398808,"id":"Q4398808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2041983$F48E904B-C3E1-45B3-B667-AEAEBEDB6576","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"300f5859ed2fc924a42b7621b9df7c52f07b739c","datavalue":{"value":"10.1007/S00453-021-00813-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2041983$67B3DF95-7F3D-4DFF-B1D8-5DFF663D9301","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"928577ff746849f9a4884cffe3f2f9eaeaf289b9","datavalue":{"value":{"entity-type":"item","numeric-id":5875558,"id":"Q5875558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90a79e38785a62164af220287513573b2d11000f","datavalue":{"value":{"amount":"+0.995745062828064","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":"Q2041983$94442BF5-9D28-4AE2-B5D5-0E6833E00107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ce6f8ae0bdc52403691b7a765fd1df1c2b0fef3","datavalue":{"value":{"entity-type":"item","numeric-id":5737815,"id":"Q5737815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7da1815b272ea0eae0f99fa14d0939ea7d534547","datavalue":{"value":{"amount":"+0.8517333269119263","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":"Q2041983$354B0EB9-C4B0-4292-987B-247F3AF151E7","rank":"normal"},{"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":"5b913d40b7cca986bdc0e78603af8f0ec62b98d1","datavalue":{"value":{"amount":"+0.8003918528556824","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":"Q2041983$A1C0BB92-221D-4C8B-A794-250BE12D1B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7384869f2236c7f12d0dfc56bea9acbfeac0404a","datavalue":{"value":{"entity-type":"item","numeric-id":5122162,"id":"Q5122162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0581b2347a18d076404bef5c7eabe2a14ba7b16c","datavalue":{"value":{"amount":"+0.791148841381073","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":"Q2041983$9E3F9F22-9D97-4ABF-AED2-48810A67D20A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e903da97decdebd0d647d4df124e0c6a136d0b0b","datavalue":{"value":{"entity-type":"item","numeric-id":2965515,"id":"Q2965515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"264a73973f95ff8a033576f31470a78812c7caff","datavalue":{"value":{"amount":"+0.7685934901237488","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":"Q2041983$8098163F-F6AD-4232-930A-73F748B6E570","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2041983","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2041983"}}}}}