{"entities":{"Q1035684":{"pageid":1037532,"ns":120,"title":"Item:Q1035684","lastrevid":66089739,"modified":"2026-04-12T07:28:58Z","type":"item","id":"Q1035684","labels":{"en":{"language":"en","value":"A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5624933"}},"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":"Q1035684$1CC1DC20-CF2E-4475-896A-EE43DFF66017","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b871fcf74954f7dc3da782bc0dff1b7464d2be33","datavalue":{"value":{"text":"A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1035684$A0DFBCA1-96D1-4ECD-99D2-E0E38816915A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d4d80c85d33d90d6fcea488f03fd2d2d71d132cc","datavalue":{"value":"1205.68509","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035684$DD3844AE-D107-4227-8169-7348DD709705","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84c2d4777f2744b402998b7945adfbeb22c23961","datavalue":{"value":{"entity-type":"item","numeric-id":1026046,"id":"Q1026046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$F3B13733-ACD8-4461-AFBA-3AEB99B21F11","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$A8EF81A4-8D47-435A-8968-A96798090FA1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ef2b4a391107c8565fc25ba0caa09f7f59741046","datavalue":{"value":{"time":"+2009-11-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":"Q1035684$216A9B4D-B2A4-4918-BAFF-8BD19EC04FA0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035684$F47C2C09-F836-4506-A65D-7716F19CDEFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca8c16691e9ec83d46a3995338b09d48ac9660ac","datavalue":{"value":"68M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035684$028F0071-ED11-4DE4-B5BE-07C7EDA7C416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035684$6B29760F-A266-457B-B51F-FDAD4BCF7D0C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dee145ce3e24e05bc7f270dabe94ffda4f0efb53","datavalue":{"value":"5624933","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035684$3FE9AD7A-47E0-49D8-8110-D148057A2BBB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035684$B8D253CE-5FFE-4792-8BB7-CA050B8A8291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c5be6e2610e5620e602cf0a17f6bc410aebc05f","datavalue":{"value":"push-relabel","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035684$EB575E12-01EC-48B1-8EEA-DFC5C6F0A1BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8851ba8890fff28d8825605e170f31e73daf2ef","datavalue":{"value":"degree-bounded network design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035684$88B2E0C0-7497-4590-BCBE-D0B8764496B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79fea923fe257428a15567ac9a4393a98e6d9e26","datavalue":{"value":"spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035684$D631F84D-833A-48B7-AFD0-16CCFF57D2B1","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":"Q1035684$5E951A32-2104-4FA5-8AC8-FE576C3DAA69","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e4228af1a8cb79e29440d084ffa062a290a77377","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2009.07.029","type":"string"},"datatype":"url"},"type":"statement","id":"Q1035684$253BC3C9-992B-48B1-8534-85F770A536F0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"536deb6293f47813a1c565c800aa6722f1249c1d","datavalue":{"value":"W2083383617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035684$758BBF92-F70A-4D17-BEBA-04BE80C64796","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"37ebbcd484fed680d8c4163479c63810627e71b2","datavalue":{"value":{"entity-type":"item","numeric-id":5302102,"id":"Q5302102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$D8D3A167-7B91-48CA-9672-40ADCB89B47D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c74df5168edb5aeca6a91300a5c054e62482ec4","datavalue":{"value":{"entity-type":"item","numeric-id":5361599,"id":"Q5361599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$CDC284A4-9401-4BAD-82C6-00C878A38644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c483e5961ca0e6e3ee610e12a19c2f28652aa0ac","datavalue":{"value":{"entity-type":"item","numeric-id":5479356,"id":"Q5479356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$D72F0610-4D6B-4A90-8819-A899FFC6C337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf234c11152e099856f8912ddd00685b4ff1a7c6","datavalue":{"value":{"entity-type":"item","numeric-id":3613760,"id":"Q3613760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$2FB47D63-67FE-4AD5-AF12-CB6C19FEDDA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$8C8410F5-1D39-4402-8999-B81FFC959374","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dd6d9ae660e25cf6e630494c601c181d753df8c","datavalue":{"value":{"entity-type":"item","numeric-id":4314499,"id":"Q4314499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$960A87A3-C2E8-486B-A69B-724335905B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14e950e9343df30ace9ab5b64fb08f94d60099c1","datavalue":{"value":{"entity-type":"item","numeric-id":1180833,"id":"Q1180833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$79C9DD06-E224-48C1-B5CD-D2E7E7F43CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64880b862c8310c1d8e7e97f8a51fba0fa2ae564","datavalue":{"value":{"entity-type":"item","numeric-id":1028423,"id":"Q1028423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$2813E9CF-7563-41E2-AEA7-8194A199409D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e66d07f72fb80fb234e471f38e6c7065a6ad8037","datavalue":{"value":{"entity-type":"item","numeric-id":4877523,"id":"Q4877523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$E1B33EE5-501F-4D08-B079-B577A5D97A39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d2e6295806da5f275a0d5240db41bd555302c27","datavalue":{"value":{"entity-type":"item","numeric-id":3503852,"id":"Q3503852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$87DB920E-5C4D-4E74-BAA3-1938EDE0566B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cc53416805904066d54b9481ef49e1b7705fa4f","datavalue":{"value":{"entity-type":"item","numeric-id":3149894,"id":"Q3149894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$55BD9EAF-BA86-462F-ABD2-2B767A075C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f1298f974783d7953f23374cb8a9441bbae503c","datavalue":{"value":{"entity-type":"item","numeric-id":3581300,"id":"Q3581300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$10044493-1539-4396-AAA9-BA6156235641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f71c43ff18750ab1c5c18d164808ad4544e81cb3","datavalue":{"value":{"entity-type":"item","numeric-id":3549666,"id":"Q3549666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$99C68722-D598-43D1-A1EA-2BC80E96A2F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06e9f2cc9027ea3a2e9a43d46098902474df1121","datavalue":{"value":{"entity-type":"item","numeric-id":5302101,"id":"Q5302101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$044D04CC-ABC7-4B42-848F-7158DBDC50E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b56ed418b4cf68bf008580e23ec8cb70de24f2d","datavalue":{"value":{"entity-type":"item","numeric-id":3343801,"id":"Q3343801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$F57E7335-3B77-4F63-8FC9-F515FFA4A94E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2aac2cfd0dc9d42086cb27fc9b5311e4e40c4c06","datavalue":{"value":{"entity-type":"item","numeric-id":3613758,"id":"Q3613758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$A58C7291-D948-48D6-92C8-E9C29150CE6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c01149a6900c0f611a509645affd60c9a396109","datavalue":{"value":{"entity-type":"item","numeric-id":1854113,"id":"Q1854113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$055DA061-1BD4-429F-83A4-31ABF54D3F9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b27909206ade5b263b26b39f27c396a5a0f02bd4","datavalue":{"value":{"entity-type":"item","numeric-id":3549667,"id":"Q3549667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035684$C0590E1F-DA45-4440-AE61-A2F5B0C413AC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"26f29555ba3b120649bc02f272d09272077cbf6d","datavalue":{"value":"10.1016/J.TCS.2009.07.029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035684$8B5EA7AF-3EDD-4960-A5C5-AF2C6102A10A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8718344d66d9a496169110fc1c1bdf9665075b2a","datavalue":{"value":{"entity-type":"item","numeric-id":3613760,"id":"Q3613760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1dcb282025d3bcd8152d53985652d9d61010549","datavalue":{"value":{"amount":"+0.919991672039032","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":"Q1035684$87C870BA-280F-46C9-A300-A5B328C30408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a13dafe1cf431302f4f88371a4186cdd2f8cdfd","datavalue":{"value":{"entity-type":"item","numeric-id":2391179,"id":"Q2391179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c8122dfb230888d86beb8dcf18fae700f3c8832","datavalue":{"value":{"amount":"+0.8545204401016235","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":"Q1035684$88D5C53E-AD0A-4620-9F8C-73BF8AF751AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be665748942ebaaa1f356105f55442d0695e0e18","datavalue":{"value":{"entity-type":"item","numeric-id":5479356,"id":"Q5479356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61870118dff50b776d541d6772b5918f6d09ab65","datavalue":{"value":{"amount":"+0.8308545351028442","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":"Q1035684$D1BAA122-A8C3-4F16-80BB-C7A84A07C06E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f1aada13b8997d4070b29dee31009045afd7969","datavalue":{"value":{"entity-type":"item","numeric-id":3149894,"id":"Q3149894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86aa2baeee9719576b43424fd5c6608671785361","datavalue":{"value":{"amount":"+0.8218467831611633","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":"Q1035684$4B12BDDA-116C-46EE-AAC4-9F5B683C3152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a12bd7f159094d3497b374985d433d51bb438aca","datavalue":{"value":{"entity-type":"item","numeric-id":3192023,"id":"Q3192023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7914503655e8049f0e2df866262f9bdcb9355bb7","datavalue":{"value":{"amount":"+0.8199598789215088","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":"Q1035684$C676D9EB-D0C4-4ADC-994C-E73D1E14BB94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_push-relabel_approximation_algorithm_for_approximating_the_minimum-degree_MST_problem_and_its_generalization_to_matroids"}}}}}