{"entities":{"Q2287480":{"pageid":2298223,"ns":120,"title":"Item:Q2287480","lastrevid":71767878,"modified":"2026-04-14T00:25:04Z","type":"item","id":"Q2287480","labels":{"en":{"language":"en","value":"Width, depth, and space: tradeoffs between branching and dynamic programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7154082"}},"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":"Q2287480$068097AE-9AE6-48D8-9559-F901DE2E93CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6628461de6b159feaf6c5bb8401287267748e0b7","datavalue":{"value":{"text":"Width, depth, and space: tradeoffs between branching and dynamic programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2287480$41A6A64A-E737-4FA8-A5A8-1877C465FAE6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5dc21234e61b7f8c4755b5a91120f4fdeb67792f","datavalue":{"value":"1461.68147","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2287480$138A5DBF-4602-4944-9D29-58026F20AE7B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a7dab8b6f9b2979c1919d172fda946cbd85cf981","datavalue":{"value":{"entity-type":"item","numeric-id":306104,"id":"Q306104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$570E3075-FC2D-45FF-9B59-09E1506E7ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00830177473b95315a508d6615caec2a5730568c","datavalue":{"value":{"entity-type":"item","numeric-id":340579,"id":"Q340579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$546FCF8E-968B-462F-9A61-BC1892DE22B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b649ac41c270dccb8d2c710d97ea2a08b9b1f33a","datavalue":{"value":{"entity-type":"item","numeric-id":340580,"id":"Q340580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$DCBA27FE-4C8A-430E-9A72-A4EB7B09C099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb319c141bca095032da90797b7c580880b492d9","datavalue":{"value":{"entity-type":"item","numeric-id":340581,"id":"Q340581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$50F50EE4-466E-4AA6-B104-6748357C475A","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":"Q2287480$4F10ADF1-12C9-456F-AC94-34262071ED51","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3a33e9289a41a440ea82601c0f5c7fc7756e3797","datavalue":{"value":{"time":"+2020-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2287480$62C8DBCC-D8FF-42A2-A176-8705F2DD772A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"454eedf6b41ecd0840f3d750afe1d38b8990439c","datavalue":{"value":"Summary: \\textit{Treedepth} is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this additional structure. On the negative side, we show with a novel approach that the space consumption of any (single-pass) dynamic programming algorithm on treedepth decompositions of depth \\(d\\) cannot be bounded by \\((2 - \\epsilon)^d \\cdot \\log^{O(1)} n\\) for \\textsc{Vertex Cover}, \\((3 - \\epsilon)^d \\cdot \\log^{O(1)} n\\) for 3-\\textsc{Coloring} and \\((3 - \\epsilon)^d \\cdot \\log^{O(1)} n\\) for \\textsc{Dominating Set} for any \\(\\epsilon > 0\\). This formalizes the common intuition that dynamic programming algorithms on graph decompositions necessarily consume a lot of space and complements known results of the time-complexity of problems restricted to low-treewidth classes. We then show that treedepth lends itself to the design of branching algorithms. Specifically, we design two novel algorithms for Dominating Set on graphs of treedepth \\(d\\): A pure branching algorithm that runs in time \\(d^{O(d^2)} \\cdot n\\) and uses space \\(O(d^3 \\log d + d \\log n)\\) and a hybrid of branching and dynamic programming that achieves a running time of \\(O(3^d \\log d \\cdot n)\\) while using \\(O(2^d d \\log d + d \\log n)\\) space.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2287480$B7C6F0EA-3FDF-4D5A-9502-7CE527A8F276","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2287480$3B09E1AF-64C3-4CD3-B8EA-A5473C1FC273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2287480$4FB2B87E-A00A-4C92-9F8B-C849376588C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2287480$22D7E639-215B-4547-9CC4-80F0D154B7AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2287480$5DD00CA5-EAA1-4111-B2CA-3AAC637371E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"58eef4f32c0cd6a5b37784af97a068d510e76f0d","datavalue":{"value":"7154082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2287480$86E8FF26-BDBD-477F-A03A-555F92A71320","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q2287480$255D1DD6-C779-428D-A15C-95D9969191AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fc6945142c143a162622d38a388d04a8c8fcc56","datavalue":{"value":"treedepth","type":"string"},"datatype":"string"},"type":"statement","id":"Q2287480$8B66E3A1-D5D6-4FD4-A8DA-EAB2FBE47BB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2287480$981F02DB-6AB5-4004-8BC6-2C5D46F3ECFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09392b50b6e9a1e27d3279972e3d1eaa31da42fc","datavalue":{"value":"branching algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2287480$04456479-43DF-4952-B080-63FE32B8D5B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"683a94a92de8b42212cff7e2fc46d5f897f7da9b","datavalue":{"value":"space lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2287480$B8172881-7FA5-45FE-AD93-9047A416091E","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":"Q2287480$19AB9BAF-A96B-4E75-A40B-4A1F670451BF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6633e6c34bcd7acb476bd906847d86b071aba93f","datavalue":{"value":"https://doi.org/10.3390/a11070098","type":"string"},"datatype":"url"},"type":"statement","id":"Q2287480$5C4A9C54-D4F7-4383-BC2F-BF605F45CB33","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9dc151a411a85f5e0f5c70c58b1329d5f1b54f02","datavalue":{"value":"W2809938360","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2287480$5FCDD6C3-64C5-4B44-995A-9841933F44D1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1820e24c3b9d2f77fdff3ae18b4874b3d9f3cb9","datavalue":{"value":{"entity-type":"item","numeric-id":3659015,"id":"Q3659015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$57DF8C05-E7FA-40F9-923B-B9D8F750D0BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a265174657273e2afc901414a2d94c245c854b8f","datavalue":{"value":{"entity-type":"item","numeric-id":3662515,"id":"Q3662515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$D03CFD27-B228-4B07-8FD2-804B1E05E2FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71c5c90fec6c5228433dfdc8a2179adec0cf5d6c","datavalue":{"value":{"entity-type":"item","numeric-id":3938489,"id":"Q3938489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$700EE898-3F68-4D95-A3D2-6455C9A49404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e512996f28cf7921ca21c9926b368100368605cb","datavalue":{"value":{"entity-type":"item","numeric-id":1122503,"id":"Q1122503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$522B5443-28C6-4E8E-8859-FE275AF4C878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca5549e5a51af06b830af5cab65cab420cc150b7","datavalue":{"value":{"entity-type":"item","numeric-id":4388986,"id":"Q4388986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$09C221C8-3142-47C4-BC83-A407EBE71420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04de0a6a1db5ffd08902686226cf000192dcf090","datavalue":{"value":{"entity-type":"item","numeric-id":1896351,"id":"Q1896351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$558895D2-B0CE-435D-B57C-90E03CF0092B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1126028165ed25aec0b23ea9dd66a35457a4e03a","datavalue":{"value":{"entity-type":"item","numeric-id":419416,"id":"Q419416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$A84D453F-62C5-43C0-A4CE-0EFA1D28D2A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7866193b7a136e602fec0331b2357cd47c045aa3","datavalue":{"value":{"entity-type":"item","numeric-id":2842148,"id":"Q2842148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$D4DF127E-3C05-49FE-938B-4B25C8DBE29C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04afb920dcbdd566b5095cb464f5623e6fa08fe9","datavalue":{"value":{"entity-type":"item","numeric-id":3452829,"id":"Q3452829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$CD26B5EC-1806-4168-A1C3-DA37B3DF9F32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fed39d42ca2b2dd840b667cc91f78a1d8b8fb44","datavalue":{"value":{"entity-type":"item","numeric-id":1686224,"id":"Q1686224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$54636E54-A39C-433A-9E15-AEAC3A7C9990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65d2cbff2fd33f30cc6d3862c866afa2ea894ca2","datavalue":{"value":{"entity-type":"item","numeric-id":2316938,"id":"Q2316938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$E0D9B3CB-E7AC-4A11-A981-2CB205AC4D91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0e64237b593672097d0a8b6a4794a25677f0429","datavalue":{"value":{"entity-type":"item","numeric-id":2411033,"id":"Q2411033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$40E58762-E577-410B-B114-1498C5DBCD48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5762d647bad67eb99de6bbf40a6d31cb9ada3a18","datavalue":{"value":{"entity-type":"item","numeric-id":5365080,"id":"Q5365080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$B45C6CE1-C021-4067-A139-EA049E700AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05ba062e35f5b9f4b7072a7b25dd2ea1a17ea1d6","datavalue":{"value":{"entity-type":"item","numeric-id":3795218,"id":"Q3795218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$A036E97B-6C58-4FB3-A88E-6C7BDB4CD61D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d92b7073011bb1b4985d7d526f565ba0b3fbd9f1","datavalue":{"value":{"entity-type":"item","numeric-id":4699283,"id":"Q4699283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$392A9E21-7B6D-458F-B922-2900DFD44841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61b134ae9f2a39b834a8ed4bf8240c4c13c1c497","datavalue":{"value":{"entity-type":"item","numeric-id":2908539,"id":"Q2908539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$7FD5B957-2183-446D-AB5A-5A095FC35C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"baf3294de56e3f9005571cbddd852d883af5aff5","datavalue":{"value":{"entity-type":"item","numeric-id":1186787,"id":"Q1186787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$7244EA3F-6812-4B68-8BE5-34906367D85F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d87478746e093073c1058b3d3f46e28a2e987337","datavalue":{"value":{"entity-type":"item","numeric-id":4728259,"id":"Q4728259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$D81A0941-83F3-4483-A8F1-0117898925B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04c961f6e5762fec9ea17404659da4eaa0b70d0d","datavalue":{"value":{"entity-type":"item","numeric-id":2561771,"id":"Q2561771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$592EBA8F-678C-4B1F-A5F8-726AFAF1C51B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3e83631d93766ff1252a940a233f265e5278ab7","datavalue":{"value":{"entity-type":"item","numeric-id":3639275,"id":"Q3639275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$61D32E8A-CE5E-4078-86A2-9FAC4FFCB6E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3df499f57db6ea2558ea92ba2027ece7930c8d74","datavalue":{"value":{"entity-type":"item","numeric-id":430838,"id":"Q430838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$C2DAD1DD-5BFC-498D-8224-49A2C385F051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33c266b6c77a64db0e80774d085cd14c5e473c84","datavalue":{"value":{"entity-type":"item","numeric-id":547305,"id":"Q547305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$DBDF546C-F469-4DD4-8E40-0EEC473EDDD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac701ad4743c38098dd53e38af774a46bd3a2796","datavalue":{"value":{"entity-type":"item","numeric-id":3832081,"id":"Q3832081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$B0C3FBE9-688E-4811-9E6E-497D62B28709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebfc0a861e4068dcb796730e240203b79ef7b5ea","datavalue":{"value":{"entity-type":"item","numeric-id":5538317,"id":"Q5538317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$619E62C5-E8C2-457E-ACA1-B120CE68D8A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3ccd52480738f16f133e453f288930971d4db9d","datavalue":{"value":{"entity-type":"item","numeric-id":4962605,"id":"Q4962605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$D0525AF5-581F-41CA-B84B-C148DF1C84CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a9fc0559f3e12a36e44f2944e66e9ecd39799d0","datavalue":{"value":{"entity-type":"item","numeric-id":4606306,"id":"Q4606306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$67CD14DF-481A-476B-95B6-8BA5FA51F84F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b25f9d90cbcc28e3f73f79a5515d30dc34194913","datavalue":{"value":{"entity-type":"item","numeric-id":2875160,"id":"Q2875160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$720EB927-4213-41B5-AA96-E8E0ED912C19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb1a444005a788404864c91f8cc0f78cd6687d0","datavalue":{"value":{"entity-type":"item","numeric-id":4601909,"id":"Q4601909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$608B9A2D-74B3-4F89-8F83-540D6F25F75F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62e967816953cecad41268e715794a55d56323d","datavalue":{"value":{"entity-type":"item","numeric-id":3577833,"id":"Q3577833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$06CCE002-CAA7-4783-9526-5925FDC7C726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f6f0e024114319e5eb6aae9883a0233df2f35ab","datavalue":{"value":{"entity-type":"item","numeric-id":3549598,"id":"Q3549598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$C06EA5DB-5AB6-4C25-BB37-DAEEF7C5D0D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"606a9799e9c2cb6c868537683690659f98912300","datavalue":{"value":{"entity-type":"item","numeric-id":4377448,"id":"Q4377448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$22AFB97A-3AA7-4A32-88A6-A46318588173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"296f973d6bb46e48f6285b5f91163c2cfb5eb389","datavalue":{"value":{"entity-type":"item","numeric-id":1759681,"id":"Q1759681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$D60B9797-D128-49E4-BAA7-EB2E8D534E07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23d7903ab5bc0ebbd173e665f10d9b2095d616c1","datavalue":{"value":{"entity-type":"item","numeric-id":2957485,"id":"Q2957485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2287480$6337C0F4-B69A-4A00-9B1B-F0A88AC891A8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9383730efd08995862369d8822e20fcf10158807","datavalue":{"value":"Q129599117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2287480$82185496-2877-47F9-95ED-3A83BBF5638A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4cd2702a35469f145a2369dab4297144830b88b4","datavalue":{"value":"10.3390/A11070098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2287480$9BE02378-E048-41AD-9337-3A1DBE8DB10B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8891e95f320d779208aef22177a67578cb2aa9cb","datavalue":{"value":{"entity-type":"item","numeric-id":2411033,"id":"Q2411033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea17541291324695ef21e38e5d1e9d0b82892bfc","datavalue":{"value":{"amount":"+0.8101447820663452","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":"Q2287480$9AF62F28-5E1B-449F-A09E-32D81588B640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58312660d9e96f8e3c8cde7447e46ed414bb6d0d","datavalue":{"value":{"entity-type":"item","numeric-id":4973895,"id":"Q4973895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ee3aa0f11a7d3044b6b2a7496af615da733d369","datavalue":{"value":{"amount":"+0.8078562617301941","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":"Q2287480$6641E745-6E00-46C9-976F-42F68F8856DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81acce75728d5ada0d509b945f19fe41426c9733","datavalue":{"value":{"entity-type":"item","numeric-id":4601909,"id":"Q4601909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"972065873c5f033a650ca3d867d0514f869fbbab","datavalue":{"value":{"amount":"+0.7999303936958313","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":"Q2287480$CD799FBA-91E4-4BFB-AF38-1CBF13E96641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"262c40cae3433123548e88d78453df85b663ea45","datavalue":{"value":{"entity-type":"item","numeric-id":4981176,"id":"Q4981176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"213554f03c556b6e2c54d7bd5c5f6143d1477955","datavalue":{"value":{"amount":"+0.7751680612564087","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":"Q2287480$0AECDB90-264C-43FA-AEE7-363E0B74C411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"015fd38dccd9b0d89d28f8c275584f31c3540764","datavalue":{"value":{"entity-type":"item","numeric-id":3196398,"id":"Q3196398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a0b4d361c76b1be35c85ba454b7f6ec16b68159","datavalue":{"value":{"amount":"+0.7737868428230286","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":"Q2287480$6864449B-0C6D-4F7D-8EAF-1F5C985AE6CE","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":"Q2287480$6E55AB27-425F-4BF7-AC94-F2AE6EF82B7A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Width, depth, and space: tradeoffs between branching and dynamic programming","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Width,_depth,_and_space:_tradeoffs_between_branching_and_dynamic_programming"}}}}}