{"entities":{"Q1086497":{"pageid":1097249,"ns":120,"title":"Item:Q1086497","lastrevid":66419481,"modified":"2026-04-12T09:57:00Z","type":"item","id":"Q1086497","labels":{"en":{"language":"en","value":"Edge exchanges in the degree-constrained minimum spanning tree problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3985001"}},"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":"Q1086497$E87250C2-4104-4C27-BFA9-AB41215BAC70","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa581c3022f09ac8401fd4ded28781beb95a23b1","datavalue":{"value":{"text":"Edge exchanges in the degree-constrained minimum spanning tree problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1086497$4997D00F-E3AF-478D-9A7E-DAF29EAC111F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8a60fece2bed98379942cd52dd506dcc5f595194","datavalue":{"value":"0608.90098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086497$78280461-EBFE-42AF-8CD9-3C02FC0B54AF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d809b7b466d23dec6f630aa51ba5e0761976584","datavalue":{"value":"10.1016/0305-0548(85)90032-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086497$0CD01AAB-C97A-4658-887B-A7DD092D646E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a981753343b2f01f33403fe406af396c6839ce8","datavalue":{"value":{"entity-type":"item","numeric-id":759660,"id":"Q759660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$7E4CB295-00CD-43A9-97CB-CBD8E6F62220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"74d443459ea69034427e7e35e307e316372f4476","datavalue":{"value":{"entity-type":"item","numeric-id":163010,"id":"Q163010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$79A8DC01-28EF-4B8E-88C0-BA50A3A486BF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e630590c5ca6e787c3c7b5e291898405495fea2b","datavalue":{"value":{"entity-type":"item","numeric-id":162215,"id":"Q162215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$85796788-4B58-415C-85FB-BF14B58EA145","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1086497$904A8F63-362F-4B0A-95F0-A76BA6A9AD7F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0702a09aa07209d779b853604fec41e1db87308e","datavalue":{"value":"We describe a branch and bound algorithm to solve the degree-constrained minimum spanning tree problem. We propose an edge exchange analysis frequently used in the algorithm and three types of heuristic methods. Computational results are reported for problems with up to 200 vertices. These results are much better than known results from the literature.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086497$AFD533A0-98BD-4B07-995B-26038C2B1E41","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086497$12EDD8A5-5113-4A08-BF69-9C88575D9FE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086497$D2ADDCD2-AE1C-4250-8BFF-FADC343887C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f4a9ad77b9ee24429815386d5396d748c13212be","datavalue":{"value":"3985001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086497$EEF6C467-BE75-4AF3-8489-BE36236DE296","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086497$5370706B-6B6C-4FCA-B588-BC49B167A636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00bb4087d7fb04ca13a2f130dc6597ec71a318ac","datavalue":{"value":"degree-constrained minimum spanning tree problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086497$EF2D1A6E-3978-4B66-A7F2-7AE06DE4D26F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63496001826d6d71478a7cbc4cae2bf7f4eedba7","datavalue":{"value":"edge exchange analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086497$A055854A-02F0-4A7C-B096-91E9D19F14CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2661a0360bf1e96bc1f5b465a8070ac88ffa8a5b","datavalue":{"value":"Computational results","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086497$F2BFE7C0-9147-4598-8B10-D05F76FC9711","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":"Q1086497$70825FC1-8B20-49FC-977A-D5D11A967F14","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e5d8fd017ea3b5168f5d2110de2b2f881b5bbc15","datavalue":{"value":"https://doi.org/10.1016/0305-0548(85)90032-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1086497$427CFDB5-BE94-416C-81EC-162D52D162ED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"603da273e030d5f281374950bde7405ce9b2e9a5","datavalue":{"value":"W2033983963","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086497$32E83FCC-E9C5-45F7-A768-EE6F446F6813","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9586825a9df16830137e7d33acb174b1d38d8c12","datavalue":{"value":{"entity-type":"item","numeric-id":1158108,"id":"Q1158108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$3CA9AA8C-6831-41A5-9024-C9C3494D6DCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb2ca458acea0e3632727170dcd237e7765fa59","datavalue":{"value":{"entity-type":"item","numeric-id":5514188,"id":"Q5514188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$FE0A9F47-0D81-4589-9085-4D691F72BA31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f85f1bb9a2b42e8fd917505f47354b45d357319","datavalue":{"value":{"entity-type":"item","numeric-id":1170119,"id":"Q1170119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$69F2644F-55E8-42A3-A038-D4AC07A7D97B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$3757486D-FEF2-41BE-B9CE-0CC04C3C6C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddcb0e3becea206f28da927b7987a0722a8c7a6d","datavalue":{"value":{"entity-type":"item","numeric-id":1086497,"id":"Q1086497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$3666EEDE-E83A-444F-8221-D74F7589BE60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b5b903864765fb40a5b80f7f222eabf61ff3f0c","datavalue":{"value":{"entity-type":"item","numeric-id":5641007,"id":"Q5641007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$EF2BAF9C-1F24-4234-B2FE-827570BB7237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a6fa9559301ce050aa6bf99068d2ede5c82fef","datavalue":{"value":{"entity-type":"item","numeric-id":3956857,"id":"Q3956857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086497$E95692AB-D632-433F-90E1-12425DEBB468","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce11b0d21d62567a41bf855bdd0100781d8ac876","datavalue":{"value":{"entity-type":"item","numeric-id":2221985,"id":"Q2221985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb193d82c576311054e8670f9846fd6f96a64902","datavalue":{"value":{"amount":"+0.89227146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$065300BB-BA39-4AA6-A344-358D699BE9E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a098668913b3e7e95effcc3c131a33053093e07","datavalue":{"value":{"entity-type":"item","numeric-id":5955562,"id":"Q5955562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3db0cefea627c379433584375b114314e59be47a","datavalue":{"value":{"amount":"+0.8893919","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$C23CC8BE-4331-44D7-B4F4-6D77A509BFDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29506b5a339f1af099fe729b8e50f9b77296fc93","datavalue":{"value":{"entity-type":"item","numeric-id":358656,"id":"Q358656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24e92f2881d8af84c69494d2d8dbd48642118dda","datavalue":{"value":{"amount":"+0.8880881","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$1C890C0D-FEF5-4663-BF54-5926220FCAB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfe8eba722cdac12edc6b10a1007e1658c2bbf8e","datavalue":{"value":{"entity-type":"item","numeric-id":1848629,"id":"Q1848629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad7162125509f16ad4996c344e7986535b85e7f4","datavalue":{"value":{"amount":"+0.88384706","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$A53B27A4-F742-4911-8BB3-14C8A8E5EA7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbc43ca3a96844d65240f1e8b52125d35183bece","datavalue":{"value":{"entity-type":"item","numeric-id":2914198,"id":"Q2914198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34262cdd2a5ae32ee67750b4874a8a281b2d203c","datavalue":{"value":{"amount":"+0.88229775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$F06E1315-8A71-40F6-AB4B-DF86CA03C9A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a9f5f20db19ea187eb5579b916c5fa29e889c52","datavalue":{"value":{"entity-type":"item","numeric-id":2790350,"id":"Q2790350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c05278254e411ae1926ee86408ecb81e3c48fc79","datavalue":{"value":{"amount":"+0.88094735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$C48BE145-640C-4E84-94F4-DC10898DE8BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"360d52948ce2ef3f341aca127dbb44267eb1345e","datavalue":{"value":{"entity-type":"item","numeric-id":1209313,"id":"Q1209313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40dfb20394941e47bda5e3194615e098254c92de","datavalue":{"value":{"amount":"+0.88032913","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$6DFE7DE5-78B6-4139-BA79-1A899E940D2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8752b042d96b40963e9d17f552c2dd37c65a5e5","datavalue":{"value":{"entity-type":"item","numeric-id":1892100,"id":"Q1892100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"100eeb7c0b870adc68689eaf75207c13d07c785e","datavalue":{"value":{"amount":"+0.87997544","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$2B1855A1-4364-4DCD-BB4B-DD0FE0A73B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cac7fdd53bf8cc82d6a24432593718186ce47ed","datavalue":{"value":{"entity-type":"item","numeric-id":3593370,"id":"Q3593370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3546ee1e4599689865c65f74f0c5584d8eb733bb","datavalue":{"value":{"amount":"+0.8788477","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$A52D4134-D852-4719-920B-40282679CDE9","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":"969b4e7f312cadff51836be53ca8ebeb5f3aec8d","datavalue":{"value":{"amount":"+0.8783498","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086497$D8D841CC-D793-49A2-8D8B-644604FDCBBC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Edge exchanges in the degree-constrained minimum spanning tree problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Edge_exchanges_in_the_degree-constrained_minimum_spanning_tree_problem"}}}}}