{"entities":{"Q1101129":{"pageid":1111881,"ns":120,"title":"Item:Q1101129","lastrevid":66135339,"modified":"2026-04-12T07:46:51Z","type":"item","id":"Q1101129","labels":{"en":{"language":"en","value":"Packing and covering a tree by subtrees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4045791"}},"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":"Q1101129$115C314F-BD1A-479C-999D-D725C76AB42A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0159297287f95265343c2dce11099bb421e6f0d2","datavalue":{"value":{"text":"Packing and covering a tree by subtrees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1101129$3FF84771-A95F-4195-8408-F79C90305AAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ce6979b352d4154dff85a06641816dee466c3a5a","datavalue":{"value":"0642.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101129$5D357609-527C-4A0A-B772-BB88B713CC77","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d65f9fe8d0b77299334413a19f26630600f490db","datavalue":{"value":"10.1007/BF02579383","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101129$27DFD823-C9FD-49AC-BD15-88B9971D1C88","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101129$DB00B591-AEEA-4E2D-A87C-9658A2D6CDB7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101129$1EFC0EB9-B5F2-4AEA-9D10-DCA67CE9F508","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1101129$E66D15AC-1708-411F-9199-ED4EACAE332E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dda38f6e0edccc999e60e953704fb1b1fab78cc4","datavalue":{"value":"The authors consider various generalization for the problem of packing subtrees into a tree, and describe the structure of the vertices for the polyhedra associated with these problems. They also give efficient algorithms for optimization over the polyhedra, and prove that the related problem of covering a tree by subtrees is polynomial-time solvable when the family of subtrees is ``fork-free'', using a reduction to a packing problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101129$61F638CA-661D-498B-815F-43D49ECD2709","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"67aeec512b636e4668aab1b914be3244788dfcae","datavalue":{"value":{"entity-type":"item","numeric-id":914549,"id":"Q914549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101129$7B18A27B-BDE0-4FF7-8CCE-B84C0FFCD029","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101129$0735C1F9-6589-4D0F-8B83-88D31AC0C859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101129$26FE78AA-246D-4E65-A93B-BC5FAB964AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101129$ED15E5F8-A9E3-4E25-94D3-2F2BFF880386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb6fa31c061028a10fb1c2a1679af7746583c504","datavalue":{"value":"05B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101129$51B1EE11-BC4A-4E0A-9824-1DE9E28F4E55","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"16fdb44370e8e5c25445254f1fee87e8dfa2d853","datavalue":{"value":"4045791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101129$9CC5EA06-0C4A-4CE5-B210-99D0AC1A78C1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101129$D2C837BE-F6F6-481F-AEF5-83528618DAF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05517ee236d8b1a8bc83e3d22c72a947d7e6da29","datavalue":{"value":"tree-matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101129$A67C2F08-71C5-43F9-8E66-163D8887F1D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101129$6F159AD2-853A-4AA1-AE6A-E9159B6C0D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"81600706d8106720ed4409f42180cf6427992444","datavalue":{"value":"0-1 programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101129$4BCEA72E-50D2-47DE-A64B-BE46091B34BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fcfa8c4e3781b87ae2491f62011e508c4280c6c","datavalue":{"value":"packing subtrees into a tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101129$E28545F8-EBB8-4402-A4E1-15469018D186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e75a283ce553f13dfa7f5870825606d9e54fd21f","datavalue":{"value":"polyhedra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101129$BD33D8AC-AE99-4049-8597-29D96EC3469F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101129$7A9323D9-B9C3-45AB-A2DB-D02AB0C8AC95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbae8a95529faddea0fc992737aede63492ca875","datavalue":{"value":"covering a tree by subtrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101129$23BF65D8-CD13-45AE-8A15-0C1874169307","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":"Q1101129$6BABC3EC-0C28-429A-BB52-D76EFB5E7977","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c62a000687268b18ead5e4521384e41d00b6a108","datavalue":{"value":{"entity-type":"item","numeric-id":3343777,"id":"Q3343777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101129$2B0A5C9B-1258-4464-8779-4B25ADB8ACDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c406cccfaf0baf112bd503da4f4373902a51376","datavalue":{"value":{"entity-type":"item","numeric-id":4093489,"id":"Q4093489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101129$53FC32DA-2A34-42DA-A795-57C734226C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e458531dc8f9b4a4f76ca8cb6a5d9d31ac768ee2","datavalue":{"value":{"entity-type":"item","numeric-id":2562090,"id":"Q2562090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101129$D5E08C2E-1CF8-4FF1-B5FC-35EA45D18EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101129$9FBCB78D-6B0B-449E-A4C4-D0A95676F3EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc8086da37030b484c19062884228ebe502eabbc","datavalue":{"value":{"entity-type":"item","numeric-id":3895223,"id":"Q3895223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101129$D4FC8144-6381-4627-B736-DB7EEE045C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49cd57de3077cedf167c4cfbb473079f46f9dbb7","datavalue":{"value":{"entity-type":"item","numeric-id":1838422,"id":"Q1838422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101129$0AF66706-9870-4C75-A571-82FAB59125E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"df1c5db78147d8b12a6036eb08da4ab1d5218018","datavalue":{"value":"https://doi.org/10.1007/bf02579383","type":"string"},"datatype":"url"},"type":"statement","id":"Q1101129$45266C5C-4DD7-4C57-B44D-441B9C1F2FA9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fa9633d3986f122ac7e95a16ab5fc8b9d650e503","datavalue":{"value":"W1977577374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101129$59010D15-B703-45DD-9534-9D512B2A7B9B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8642a86dc76b863cc38a4aa963ea2ceb0a8a6d43","datavalue":{"value":{"entity-type":"item","numeric-id":1914069,"id":"Q1914069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93ab773bf05dd624e17ed96ac9c4cfe1d0131b85","datavalue":{"value":{"amount":"+0.863562285900116","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":"Q1101129$6DAF4529-53B3-4997-A103-A4FBE42BAFDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"754fe7a6915e5a26ba6a802bf3a7ead8ff719cb3","datavalue":{"value":{"entity-type":"item","numeric-id":4367628,"id":"Q4367628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93ab773bf05dd624e17ed96ac9c4cfe1d0131b85","datavalue":{"value":{"amount":"+0.863562285900116","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":"Q1101129$DAD68F82-F0FA-4397-AC62-CD63515B0088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc9977c3309117a0541abbe8a132b876827bd98c","datavalue":{"value":{"entity-type":"item","numeric-id":4845371,"id":"Q4845371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2fd7470ed691414a17396895eca233c057f051a","datavalue":{"value":{"amount":"+0.8267886638641357","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":"Q1101129$545D7F31-2983-4ADD-B260-FAB98AB1592C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f7053f227cfd8ab248d54692fd451479a44ac2c","datavalue":{"value":{"entity-type":"item","numeric-id":4250206,"id":"Q4250206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e105607aa7438508f7b0d0b26989e1bc3fae5d73","datavalue":{"value":{"amount":"+0.8259291052818298","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":"Q1101129$5D52591F-81C3-48BC-8D6E-AC9C258DB13C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"439ee7d07c1da4ba425c95d112407d3f5a76257d","datavalue":{"value":{"entity-type":"item","numeric-id":1391314,"id":"Q1391314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8deaa51c6ee5fc085ed08f5b73f2a2b19e5515e1","datavalue":{"value":{"amount":"+0.8070360422134399","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":"Q1101129$1A33A704-9769-4611-A59E-D116CC3CFFD1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Packing and covering a tree by subtrees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Packing_and_covering_a_tree_by_subtrees"}}}}}