{"entities":{"Q1317004":{"pageid":1327754,"ns":120,"title":"Item:Q1317004","lastrevid":67159251,"modified":"2026-04-12T15:41:27Z","type":"item","id":"Q1317004","labels":{"en":{"language":"en","value":"A greedy heuristic for a minimum-weight forest problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 527395"}},"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":"Q1317004$E2D17564-A04B-4DC0-8A43-AB96C68307C5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b42f422fbd02165a683b170a368ae88723a17564","datavalue":{"value":{"text":"A greedy heuristic for a minimum-weight forest problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1317004$F1A5F78C-D6AA-4CDF-A0DB-DB9D2E6D51C9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8a6016c01ebdb456803d51ea6c425696be3243c3","datavalue":{"value":"0804.90124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317004$8DDFAD83-070B-4D3B-80DF-67AD5DE26FAD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"084a9b6422ce482c7cec5744d7df51476e50e119","datavalue":{"value":"10.1016/0167-6377(93)90097-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317004$2A4C64FA-A252-48A0-87D8-695ABEF5AB2F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38684b7b29cf95e44150fe068164461e3ab55058","datavalue":{"value":{"entity-type":"item","numeric-id":167858,"id":"Q167858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$6811DAA8-860E-453A-9DBE-DB618881E243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1419842bb8e98ef67f2bea44989c52cd03b97a03","datavalue":{"value":{"entity-type":"item","numeric-id":1315410,"id":"Q1315410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$2FC410C9-D5DB-42CE-BCDE-09ADF4401081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17bca481add274b6f33cca632a4c4b4a54417801","datavalue":{"value":{"entity-type":"item","numeric-id":688622,"id":"Q688622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$B041EAA5-A23C-4176-8162-A55033B5FCD5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$825A7932-AC19-46AC-BEF4-A67CC210F7B0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0afca6352c2d92a71eb1b73f58dfc4af92f3fa9","datavalue":{"value":{"time":"+1994-03-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1317004$481D1632-918B-4C52-9E55-2B77F2E19B1E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2e38fb13003a6c3ba80bd9ee960f7b788c4a3012","datavalue":{"value":"This paper considers the problem of finding a minimum weight collection of edges (in a graph) that intersect every cut set of size at most \\(K\\). For \\(K= 1\\) the problem reduces to that of finding a minimum weight edge cover of the nodes of a graph, which is polynomially solvable. Indeed, the problem is polynomially solvable for all \\(K\\leq 3\\). In this paper, the authors show that it is NP-hard for \\(K\\geq 4\\). In addition they describe an approximation algorithm which returns a feasible solution with cost at most twice optimal. The algorithms runs within the time needed to compute a minimum spanning tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317004$7BAAF6CD-C614-464A-AD1A-61A5C2027D99","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317004$CD50C53D-B369-4556-90AC-37BF65E85C76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317004$53FB63FB-6D9E-4716-8069-3D6222EE1965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317004$1E1F0A77-4A25-470B-80C4-37A54A33F871","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5664ac2e7304872917b950958d4496cd76d5eb5d","datavalue":{"value":"527395","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317004$D16DBEDE-8893-4D54-A3C8-61EA58FB19CF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd0ec47f2d4dab7908c2ebbe2726174dab4de56e","datavalue":{"value":"greedy heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317004$59AEA54E-20FA-4104-A9C6-6000CC2A65C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68f7c0d2bf53a33bff706cd32f860a42a92ac2c0","datavalue":{"value":"minimum-weight forest problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317004$129FC8F8-2796-4DCD-9B8E-D04F0A7658D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317004$C6DA09F8-9047-442F-8D6F-B1FA8371C054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af53df362fa5418f9cfe031ab74617706f64f18f","datavalue":{"value":"minimum weight collection of edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317004$98C52FD1-4DC0-4273-ACA7-1818EA70C681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"732e1592c53acfd9740f2cb8680bbb91fda5b0af","datavalue":{"value":"minimum spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317004$79552567-CBD4-4DB1-9C8E-CFF3D5EB7313","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"410981a1afadda812bc680dfed4766e5e039a80f","datavalue":{"value":{"entity-type":"item","numeric-id":581215,"id":"Q581215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$080C14B4-E752-42D1-ACF5-FA8F05AA4559","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":"Q1317004$1438F385-9635-4B30-8468-C1613020BD9D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$39EB06B4-6C27-4AE9-A7AA-46AB62215AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e97d78f2ad211155ffa5d6f2138c431781f03354","datavalue":{"value":{"entity-type":"item","numeric-id":1145707,"id":"Q1145707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$2D7D4EB2-AD1D-4401-9BCA-9C92647F08A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$1EEC95DA-7242-45F1-A6F6-4770DB501FE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44a044a04529dedacee8adfff9cbefe7d157dd6c","datavalue":{"value":{"entity-type":"item","numeric-id":4763416,"id":"Q4763416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$DF984E49-197D-423B-8CE1-4518880D50C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e12a6f3e0cdfef3dc5af3ab63e02ba088c5ffef4","datavalue":{"value":{"entity-type":"item","numeric-id":3813310,"id":"Q3813310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$9ED5D155-4F63-4026-A1CC-039D2648C876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da84027e1563413eb2614e6d2a051f9d7c7e44cf","datavalue":{"value":{"entity-type":"item","numeric-id":1361421,"id":"Q1361421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$0DC02AA2-8355-4A47-B6AD-900285192D7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7534d88e63231e4bb12474e9051539230aa7343","datavalue":{"value":{"entity-type":"item","numeric-id":3332259,"id":"Q3332259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$BC1C5464-D66C-4FF1-993B-2132864864C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317004$AB275444-34BF-4AA4-B37D-7B395BECD0E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e90fbe5acb4a90d557145793562db18aec15acf","datavalue":{"value":{"entity-type":"item","numeric-id":813973,"id":"Q813973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c296da2b1c386cb6a6eef6db7ab2843fb76b350","datavalue":{"value":{"amount":"+0.9289002","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$0C27DEC1-CC03-46B7-B983-C900F032E2F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cdfe258d44a39d2209fde0c90cfed216495bd46","datavalue":{"value":{"entity-type":"item","numeric-id":1278250,"id":"Q1278250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9e84f82a5673a6fc7415f4e305dd9e7d2e44b0c","datavalue":{"value":{"amount":"+0.9170245","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$A341399B-6980-49F8-AB97-B03B966A9714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82e8d9fcdeae41a76f375d862ebe61bb87dd32c6","datavalue":{"value":{"entity-type":"item","numeric-id":2581555,"id":"Q2581555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c09e01059ae61f4f5a7dc056e8dce3dec4fc4464","datavalue":{"value":{"amount":"+0.903668","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$1F870EA3-872C-46D0-B825-2B28CE499948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"547c12e061a1a6401e9f7811c73a52ef5a4895e5","datavalue":{"value":{"entity-type":"item","numeric-id":1278942,"id":"Q1278942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ffea77dd23dc95a4ef2e79b67d9beea55812fca","datavalue":{"value":{"amount":"+0.88711953","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$FFFFDA03-39AB-4979-9737-3CD39632E2A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5513cd1e0c49b810fc58ca2620924db5424cc71","datavalue":{"value":{"entity-type":"item","numeric-id":1891232,"id":"Q1891232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1084eee387f8d87c5bbe30b602e4a93a6c0cff07","datavalue":{"value":{"amount":"+0.8813886","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$96E51919-8370-4770-B07D-7C7743142D78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3863ce56cd95aa58d4534cd9bbe9d3b201badff","datavalue":{"value":{"entity-type":"item","numeric-id":844529,"id":"Q844529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"782cbc7c4e23a01673da3766c28a26895d94b9de","datavalue":{"value":{"amount":"+0.87339985","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$3F8074C3-4754-4112-A7C3-5C6EA947AFE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8c327154f7d08c6c82a93fbe93aad4e8bc106a8","datavalue":{"value":{"entity-type":"item","numeric-id":5406193,"id":"Q5406193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca13f74b42a926a955ac5adc34fbfdd6af45e1f8","datavalue":{"value":{"amount":"+0.8708086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$4D61122D-6F8F-4433-B5F8-2F6017829DBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7435acf219deedd13da3e84310a90f0e48111c2","datavalue":{"value":{"entity-type":"item","numeric-id":2941584,"id":"Q2941584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a15961ab4395c8e4c8f69e7fa8302f4e0a2033b","datavalue":{"value":{"amount":"+0.8669446","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$7440FDDD-03B9-4BEA-AE29-08FF9C17C0F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b14a52ff02a2782dd319333afd925249a307199","datavalue":{"value":{"entity-type":"item","numeric-id":1263993,"id":"Q1263993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f930631a4611a2c622628ef205e6d76607012e0d","datavalue":{"value":{"amount":"+0.866519","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$6DCB3EEF-02CF-44A9-8B53-F56B772AA96C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06a4f6735864017a5d1dbcb9438027ffa865eafe","datavalue":{"value":{"entity-type":"item","numeric-id":4446228,"id":"Q4446228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0fa618fe9fddf68dd9c243d5cb62b1d3c8b9372","datavalue":{"value":{"amount":"+0.8664404","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1317004$D973E8BC-85CB-4AAA-9770-944F5A5A4191","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A greedy heuristic for a minimum-weight forest problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_greedy_heuristic_for_a_minimum-weight_forest_problem"}}}}}