{"entities":{"Q442910":{"pageid":444677,"ns":120,"title":"Item:Q442910","lastrevid":57597051,"modified":"2026-03-31T13:34:40Z","type":"item","id":"Q442910","labels":{"en":{"language":"en","value":"Polynomial time approximation schemes for the constrained minimum spanning tree problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6063381"}},"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":"Q442910$527D9293-3C99-4E03-94CA-920C58D12941","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"860708ab04164b860f889dc478cef12a6cb81483","datavalue":{"value":{"text":"Polynomial time approximation schemes for the constrained minimum spanning tree problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q442910$E1B436BA-596F-44F5-8101-193E44422F02","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"82b566176c8db84818bf91a4e0c6d5fd72499723","datavalue":{"value":"1251.90373","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442910$DB5484A4-3ED4-42FD-978D-0B260721B1CB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"922928a69b81d85ffe3d4fa6ac7a03e92184921e","datavalue":{"value":"10.1155/2012/394721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442910$5A20604F-1EDA-4033-960B-3E953D4F3A3B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1bd203c2d4a8b62d10f1b829badc76f9e762b5f","datavalue":{"value":{"entity-type":"item","numeric-id":442909,"id":"Q442909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$E5CE3E7B-1C51-4D54-B667-F1F4C9802742","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bb299feb2b87699ac8beef494c52fd2765eaf609","datavalue":{"value":{"entity-type":"item","numeric-id":118601,"id":"Q118601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$80B7D096-8586-4845-A7D6-2D218D04713B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6e1e94d61bf4c54e2ef7ef4c374530b93a773f9d","datavalue":{"value":{"time":"+2012-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q442910$291709D9-BC03-4F49-8B8B-676C0EF487C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e6eefa0ddd4f23f087d800a2b3daaed5777159f","datavalue":{"value":"Summary: Let \\(G = (V, E)\\) be an undirected graph with a weight function and a cost function on edges. The constrained minimum spanning tree problem is to find a minimum cost spanning tree \\(T\\) in \\(G\\) such that the total weight in \\(T\\) is at most a given bound \\(B\\). In this paper, we present two polynomial time approximation schemes for the constrained minimum spanning tree problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q442910$F68154B8-AF0F-44A2-974E-EF4F13FCC15D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442910$2A94C175-DB95-4ABB-91D5-7CA867D77FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442910$DF14B624-E6AB-4BDB-835B-B7CEC33B020D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"69f7e8def7987969a0feba8e001d283809d3d8a2","datavalue":{"value":"6063381","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442910$DBF86532-C907-4150-9E4E-DF942052F283","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d37e8f1f29ba6bda6998ac7e0c294c299f64271","datavalue":{"value":"minimum spanning tree problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q442910$D15E77DF-D7C1-4F94-B3C0-4D2FE2FDCFDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1c84d9faf5c1ae24a1bbbed969e94094b65ef6a","datavalue":{"value":"polynomial time approximation schemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q442910$C4CD3373-D893-4860-BF90-ECEB95F9DE29","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3e5e7cabae8138981d6a7ac396f15548a6ace0c9","datavalue":{"value":"Q58906823","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442910$418CCD00-3E70-4163-AF8E-A46FDD974F12","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":"Q442910$11486DE3-BCDF-481A-8456-8070527C4A03","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3315be6175f5cb4fcdefbe35148cf211701e072f","datavalue":{"value":"https://doi.org/10.1155/2012/394721","type":"string"},"datatype":"url"},"type":"statement","id":"Q442910$0B8CA64D-6E48-44A1-9F18-BDED0824CC03","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6974ea99bd4b163719566b32db834d1c66d2a7be","datavalue":{"value":"W1977567299","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442910$BA567AB9-1CF5-4B44-A22F-8C944A7CEE50","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"acd26038edbe6565d3a8583ba4695f74dc5e165b","datavalue":{"value":{"entity-type":"item","numeric-id":4742316,"id":"Q4742316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$90E96048-B1EF-4F1F-8DC8-4591443191F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"709847060826f78126754e3059667ca59b4099aa","datavalue":{"value":{"entity-type":"item","numeric-id":294629,"id":"Q294629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$D56D67C1-BEF7-464B-A83A-2F49ED205FE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32483e6787102e8ffd7918baf6a236866fb275ff","datavalue":{"value":{"entity-type":"item","numeric-id":3664791,"id":"Q3664791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$4D66CE22-7426-44FF-B319-ADE1FC0D7C13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"940a6c288e3a8163a4796a3830b9a1c04437d28d","datavalue":{"value":{"entity-type":"item","numeric-id":4651462,"id":"Q4651462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$94EA90C3-760B-4242-B37D-79F8950228AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3eaaf7ef53ced3a9593920918cc9515489e1f159","datavalue":{"value":{"entity-type":"item","numeric-id":1426727,"id":"Q1426727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$B1E02377-F1D2-46CE-8ABD-09DF3B80BEA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67aedfa5578e7e4e96782e703990d40bf37844bf","datavalue":{"value":{"entity-type":"item","numeric-id":4268861,"id":"Q4268861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$671A2CC1-3EA7-4FAA-A07F-029B166BB898","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c3f07a6a99cf5ac0cfbc187d64d34273b5155ca","datavalue":{"value":{"entity-type":"item","numeric-id":4371290,"id":"Q4371290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$89F5EFBF-03D1-4B0D-87BC-95966F042D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$898935CF-8803-4481-94F1-B75F15DA9363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f31efddc8152c2198030e51272e5d22e52756db9","datavalue":{"value":{"entity-type":"item","numeric-id":4016708,"id":"Q4016708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$CCD6A92C-3ECF-44B2-84AC-F907B1854A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eca4801a25383ff393c8c4ac1a341f54797fdf60","datavalue":{"value":{"entity-type":"item","numeric-id":5945392,"id":"Q5945392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$73AE49CA-6CEB-46EA-8153-2161377FD163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31fe52a183314b506d7abbacebb119c015da2c7c","datavalue":{"value":{"entity-type":"item","numeric-id":1853085,"id":"Q1853085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$3DAE3DCA-0545-4116-9C17-C37BACF29813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6fc4a344d57762a56b4a664da261d7b590320d2","datavalue":{"value":{"entity-type":"item","numeric-id":2768298,"id":"Q2768298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$608D3D37-41D7-4375-AAB6-5D4AC305D494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7414675e10df7d0096ad595fbf9e8a03fa61bbea","datavalue":{"value":{"entity-type":"item","numeric-id":1401399,"id":"Q1401399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$E95E79F0-43D9-4700-BD0B-B7C2A868C965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442910$E88F3F2F-0517-405B-83A8-2D9EBFA731CC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4e6abc20821447e876c6c1946683500e879be38","datavalue":{"value":{"entity-type":"item","numeric-id":4651462,"id":"Q4651462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"612fbd43a8e30fca9a283a262a6deb9f046ac72b","datavalue":{"value":{"amount":"+0.8918944597244263","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":"Q442910$AB5C928C-CCD4-4E6D-95C9-23253B5B2B16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b03ee1ffef4a9d9748d8fb69cafdac153bf19d70","datavalue":{"value":{"entity-type":"item","numeric-id":5054807,"id":"Q5054807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb1db799d8c6d2ac5826b749f079bae3701a624d","datavalue":{"value":{"amount":"+0.8583406805992126","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":"Q442910$5AFDD76F-DA36-49A8-B036-F6E7B35D7940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"460d782f509f1675a2e27cedd1593864a5b2882e","datavalue":{"value":{"entity-type":"item","numeric-id":1699768,"id":"Q1699768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a210aa65d38d3612f1cf9463458decebbec7913","datavalue":{"value":{"amount":"+0.8160510063171387","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":"Q442910$4F7F70E2-B78F-4800-8D34-F69B5790D9B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae5e4e07d20bb604e3ae4bbe80a6e723c0e6addb","datavalue":{"value":{"entity-type":"item","numeric-id":3642863,"id":"Q3642863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f29dc757144e42c81141a469c4c564c66b597462","datavalue":{"value":{"amount":"+0.8010855317115784","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":"Q442910$9A3B83B2-34BA-4979-BCCA-FE8493E918C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b82f304b90cc6875de38e08306b6f0414556e9e1","datavalue":{"value":{"entity-type":"item","numeric-id":2380008,"id":"Q2380008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"219eace6f758c15134d6a5482aa61d36823defdb","datavalue":{"value":{"amount":"+0.8007781505584717","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":"Q442910$A7208B0C-64AE-4D5B-BD20-7219FB66A824","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":"Q442910$81968CA5-A7FC-45B8-A433-8CC062E8B34C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:442910","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:442910"}}}}}