{"entities":{"Q5885602":{"pageid":7915154,"ns":120,"title":"Item:Q5885602","lastrevid":93278804,"modified":"2026-06-05T04:07:48Z","type":"item","id":"Q5885602","labels":{"en":{"language":"en","value":"Tree-Depth and the Formula Complexity of Subgraph Isomorphism"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7672230"}},"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":"Q5885602$82FE3FF3-2745-44BD-B8F6-694857E7DFE1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7fa594098f526233414bc746c784e5b67c89b0b9","datavalue":{"value":{"text":"Tree-Depth and the Formula Complexity of Subgraph Isomorphism","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5885602$B16F8665-4950-48F0-94AC-BC51CA44C4FA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"38bfb9cc1e5a4a2564b5b1b20db084df76ed7b86","datavalue":{"value":"10.1137/20M1372925","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5885602$7444AFBC-2E14-4619-A0AD-60A2EF4F89A0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"55e874ac9bb94f248f2932e672964c908ed73d10","datavalue":{"value":{"entity-type":"item","numeric-id":2034077,"id":"Q2034077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$E55C02E6-C17B-4332-8647-55B49547C03B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"23e97eaa08b13e1bd8cce4634bd30e888245cab0","datavalue":{"value":{"entity-type":"item","numeric-id":648967,"id":"Q648967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$9D844471-0DE3-4FA9-82F1-95E19999278E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$D89E7CC0-B10B-46E7-A069-37563D9983E3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3231911715c88eeda68ab5624fcc2c3ec367b8db","datavalue":{"value":{"time":"+2023-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5885602$302BCC30-F8E0-462D-947D-22EC3E952CA9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6f462ad3720e444d7cac71162969ef9b429d55b","datavalue":{"value":"https://arxiv.org/abs/2004.13302","type":"string"},"datatype":"url"},"type":"statement","id":"Q5885602$615A1291-0512-4FF5-A3C7-CE9ED8F2BD15","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c11e1636e28bd1a59d5342c1523bca4bf56a601","datavalue":{"value":"68Q06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5885602$328D9991-B026-407B-BD1B-919E5293AFDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5885602$FA3E0972-E4D8-40CF-8075-DE9B2B35C1E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5885602$614C391F-E4B5-4CDA-9588-5E4E6F3E57A9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0bd2fc66d9bedf71eab6b22fff433101bc721d62","datavalue":{"value":"7672230","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5885602$424CC5EB-2859-4533-B7B6-FF18F672AB60","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5885602$804314E0-C9B9-485A-A14B-2208442FCBBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e50d5f5383452bd2adcef1d921f570ccfd70e04f","datavalue":{"value":"subgraph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q5885602$53045B37-0B49-4FDE-B9FB-C2811E97B33C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q5885602$6B4A709B-79E4-4457-86FE-46847BD993E8","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":"Q5885602$8736E447-4CBB-46B3-B983-E0D801F00397","rank":"normal"}],"P223":[{"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":"Q5885602$B06EF578-C4C8-4A74-A0D1-91B4E758A3C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"470bf75355798e2aee2a910e2dd7b975d3b1fe0d","datavalue":{"value":{"entity-type":"item","numeric-id":5236272,"id":"Q5236272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$0B81768F-332D-4D64-A610-2B2BB6CC94CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90a6afab494e4083533158abc4bf4359f850cf42","datavalue":{"value":{"entity-type":"item","numeric-id":4575696,"id":"Q4575696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$66D7EAB3-16C6-4E9A-A745-263DEB32D06D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f6b46dc193a243f7493903b4121f82793684fab","datavalue":{"value":{"entity-type":"item","numeric-id":4990393,"id":"Q4990393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$F6FB6685-ADBA-46C5-87FA-C8C8FB52DBA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a998553d04d92ec750c5db95c511cc38b8ab7659","datavalue":{"value":{"entity-type":"item","numeric-id":5315023,"id":"Q5315023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$CE33C55E-24FD-4575-B01C-D766BC1EB79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"688f5c774f68b5ad3a3063444a5d25297fe2080a","datavalue":{"value":{"entity-type":"item","numeric-id":4607893,"id":"Q4607893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$BC9986DE-F119-4DFF-9EE5-1EEF275F6747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d06fa39150458e3a9a117b3b190df38d0c77f1ca","datavalue":{"value":{"entity-type":"item","numeric-id":5090495,"id":"Q5090495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$D16C07F6-FABB-4DCE-8B0D-ECD1D58FB19F","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":"Q5885602$B50F1DEB-C1A4-4119-85A5-73328831BA1A","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":"Q5885602$489A8AAB-C28D-4674-B462-1E6FD7365E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b566012aa7100309ae3d6ac6ec17668692cdf74d","datavalue":{"value":{"entity-type":"item","numeric-id":2493118,"id":"Q2493118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$23A337F7-D716-474D-AE42-FBF19AA8805F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"201f2c32f4595c9ac44ae942cabbca18196e76c1","datavalue":{"value":{"entity-type":"item","numeric-id":2041983,"id":"Q2041983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$EC9C9917-2B58-4213-BC81-DF0D3B4B5F7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8184aaf98b668acd5b2f8a968bacc120e77ebfc5","datavalue":{"value":{"entity-type":"item","numeric-id":3546368,"id":"Q3546368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$4029E30E-450F-4EE1-997F-7DDBBBAE4909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f1e4d951ed7b3262e3071746a6f9304bd8b9ab0","datavalue":{"value":{"entity-type":"item","numeric-id":4601839,"id":"Q4601839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$AEF2092D-C21B-417D-A830-5BA2829E0171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6481590505bc54bd86ed7e92525eded35fd9dee","datavalue":{"value":{"entity-type":"item","numeric-id":4638077,"id":"Q4638077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$874A6AFD-0035-4C69-B0A3-5B4DAB20CE23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2832570d06b3a50da2808d5be2bfea12fe139794","datavalue":{"value":{"entity-type":"item","numeric-id":4554075,"id":"Q4554075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5885602$0BF4F901-974C-4E94-9D8A-20A49E78A140","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":"Q5885602$3001AF68-010C-4216-A64F-4B854FE9D713","rank":"normal"}],"P1643":[{"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":"cda7c9523eba00b2c5a7624e2b424b04226bb885","datavalue":{"value":{"amount":"+0.8474103212356567","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":"Q5885602$40803D94-4553-420B-A034-4186BBB5FD67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc747dc710cd924e0ed858a5d965c8da8f532f1a","datavalue":{"value":{"entity-type":"item","numeric-id":2041983,"id":"Q2041983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a1ec0f7575b27d05fca251d6ccad5a97988bf31","datavalue":{"value":{"amount":"+0.7910199165344238","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":"Q5885602$C73F2938-4266-4D81-877A-8E41249267BF","rank":"normal"},{"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":"06011de03353fc0e6b4b70d7a92a4b5667ad5a32","datavalue":{"value":{"amount":"+0.7904213070869446","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":"Q5885602$1350FAA4-5CB4-452F-8EF9-E8B12374CA18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c88fc18850961f38617353c53a51dfd4fffd29ae","datavalue":{"value":{"entity-type":"item","numeric-id":5003303,"id":"Q5003303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36fd6bd814ac788bf3f55daf0af0fc035c8f4eb4","datavalue":{"value":{"amount":"+0.7785620093345642","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":"Q5885602$379A2C79-C3FF-4433-99C6-A123D2A73C08","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":"b0196771722137b29f12d21379e9533b5797df39","datavalue":{"value":{"amount":"+0.7700698971748352","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":"Q5885602$891DBCDC-9A5B-4C1C-BEFB-8CF3B28914B1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tree-Depth and the Formula Complexity of Subgraph Isomorphism","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tree-Depth_and_the_Formula_Complexity_of_Subgraph_Isomorphism"}}}}}