{"entities":{"Q2221985":{"pageid":2232728,"ns":120,"title":"Item:Q2221985","lastrevid":57228744,"modified":"2026-03-27T13:37:47Z","type":"item","id":"Q2221985","labels":{"en":{"language":"en","value":"Degree-constrained \\(k\\)-minimum spanning tree problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7304968"}},"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":"Q2221985$811907E2-72A0-4C82-886B-B099A523128D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b6ab1136358a03cbf051a94b89978ebfad854214","datavalue":{"value":{"text":"Degree-constrained \\(k\\)-minimum spanning tree problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2221985$F786E2F6-E03D-4581-8AA4-819E5229A7D2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8fd384edc1da3b5f7db1e19ac3dd3898841c83c","datavalue":{"value":"1454.90102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221985$9BE7D385-D4B8-47A4-A36F-7ACC5CFEAC84","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"00914c3345325199469b49f76123d936489ac1ef","datavalue":{"value":"10.1155/2020/7628105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221985$373B518E-FDC3-4C53-8D96-EF66F34C60F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"157b9891bf358d1f8c221735a06663c4577dc382","datavalue":{"value":{"entity-type":"item","numeric-id":310351,"id":"Q310351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$90C5C41A-C82E-454F-A397-CA799FCDBF80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9c020376cf2fdbd661bc99194b9cdfd815a4d43e","datavalue":{"value":{"entity-type":"item","numeric-id":2221984,"id":"Q2221984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$34B7A3FB-C295-40B2-A528-8313BCEE5F9C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1dec05d6eca21826ddc25d78a5bfbbb3575f964c","datavalue":{"value":{"entity-type":"item","numeric-id":86231,"id":"Q86231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$B819C3AF-DCC7-4B79-B017-FFAB7183F02E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4fdcf569a0845156edf00801a6025e0e3cf1d2e","datavalue":{"value":{"time":"+2021-02-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2221985$654465FC-D126-4759-A9A8-113808948CC0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"46fa28072f3a9571d91ef5412c94210f7b3e7ec4","datavalue":{"value":"Summary: Let \\(G(V,E)\\) be a simple undirected complete graph with vertex and edge sets \\(V\\) and \\(E\\), respectively. In this paper, we consider the degree-constrained \\(k\\)-minimum spanning tree (DC \\(k\\) MST) problem which consists of finding a minimum cost subtree of \\(G\\) formed with at least \\(k\\) vertices of \\(V\\) where the degree of each vertex is less than or equal to an integer value \\(d\\leq k-2\\). In particular, in this paper, we consider degree values of \\(d\\in\\{ 2,3\\}\\). Notice that DC \\(k\\) MST generalizes both the classical degree-constrained and \\(k\\)-minimum spanning tree problems simultaneously. In particular, when \\(d=2\\), it reduces to a \\(k\\)-Hamiltonian path problem. Application domains where DC \\(k\\) MST can be adapted or directly utilized include backbone network structures in telecommunications, facility location, and transportation networks, to name a few. It is easy to see from the literature that the DC \\(k\\) MST problem has not been studied in depth so far. Thus, our main contributions in this paper can be highlighted as follows. We propose three mixed-integer linear programming (MILP) models for the DC \\(k\\) MST problem and derive for each one an equivalent counterpart by using the handshaking lemma. Then, we further propose ant colony optimization (ACO) and variable neighborhood search (VNS) algorithms. Each proposed ACO and VNS method is also compared with another variant of it which is obtained while embedding a Q-learning strategy. We also propose a pure Q-learning algorithm that is competitive with the ACO ones. Finally, we conduct substantial numerical experiments using benchmark input graph instances from TSPLIB and randomly generated ones with uniform and Euclidean distance costs with up to 400 nodes. Our numerical results indicate that the proposed models and algorithms allow obtaining optimal and near-optimal solutions, respectively. Moreover, we report better solutions than CPLEX for the large-size instances. Ultimately, the empirical evidence shows that the proposed Q-learning strategies can bring considerable improvements.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221985$15A2DB49-2825-41F4-A254-5E120C9D6C81","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221985$8B1C4798-8682-48B6-B178-A77086BAC69B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221985$AE31A40E-5BC4-4DA5-BA6B-BFADAF7096A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221985$487977A4-8766-4F23-9D1B-9D95614BD842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221985$B0FEB24F-A158-48AC-A9AB-57FA81902163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221985$F2357B61-E036-4D63-A581-B4BCB8E146D8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4437407762f9777515d28fe2d32e1d976598b446","datavalue":{"value":"7304968","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221985$8CCA97A1-25EE-41D9-8EE4-FDCB4CA629FB","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4d0306a541ac4d64d413698a8167f6dce4fa4ce8","datavalue":{"value":{"entity-type":"item","numeric-id":16269,"id":"Q16269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$67FB4641-CCCF-46E2-A014-2E5BA6E1491C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8bf42d0fd66acf369e3d5d44d7ebef6adc7ae452","datavalue":{"value":{"entity-type":"item","numeric-id":56651,"id":"Q56651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$421EBCE8-1366-40E2-8E52-404FB35E97E1","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":"Q2221985$1065E69F-886F-467E-A54B-3E2E08B69FB0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"27baf0e6d60e585a8791856ac1dcfc1b5c6683ed","datavalue":{"value":"https://doi.org/10.1155/2020/7628105","type":"string"},"datatype":"url"},"type":"statement","id":"Q2221985$992D6F74-4911-4E70-AF4C-90472C36C961","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"01c84b79be16dcd61b46f937cd3cf1163ca90e28","datavalue":{"value":"W3104175966","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221985$CEC5AE5E-42B7-48BA-B6D3-0E27DDDC559A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7f1e09ad03212aefa2b4df626a3bf552e2ad243","datavalue":{"value":{"entity-type":"item","numeric-id":2280295,"id":"Q2280295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$1BEC2D89-0902-45C9-92E3-DC03E3927770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8ed448e6ec31a34407da555a96866d33c0b8d4f","datavalue":{"value":{"entity-type":"item","numeric-id":1755415,"id":"Q1755415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$6DF1AFE7-4C55-4C19-A897-57E9A4094BA9","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":"Q2221985$B17798E2-526D-4776-BAC9-8F885AD24B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cccb2aaec1b0fd089776d54d6e7e048a38946578","datavalue":{"value":{"entity-type":"item","numeric-id":4881285,"id":"Q4881285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$7B85EEBC-849E-484C-904F-4805CE7C2BA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29d25f0bf6c2ad19e7f93505b389a83ac9208c7d","datavalue":{"value":{"entity-type":"item","numeric-id":2714906,"id":"Q2714906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$CD32F10C-C2A5-41B3-B07E-D4EFAA6CA0E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"056e9b3f080acc91621d1aa3202d846d459356ce","datavalue":{"value":{"entity-type":"item","numeric-id":4565761,"id":"Q4565761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$ACF7DE65-80AF-4CD0-BFEF-E60F267870DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6355a4f79308e4c64229344c6e4ecf440b6ab723","datavalue":{"value":{"entity-type":"item","numeric-id":5937708,"id":"Q5937708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$F189769E-B83B-4E29-804E-28BBCD8CBBC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07b2faa219fc3aad710e52b5e8480ff33320e479","datavalue":{"value":{"entity-type":"item","numeric-id":1374041,"id":"Q1374041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$213B8A7C-5FB8-4E7B-B81E-7DCD14C7F915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0a3a0c5f5d0b2a8e1e1ba8b6c8c54863770d1d0","datavalue":{"value":{"entity-type":"item","numeric-id":2489896,"id":"Q2489896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$72526A89-6F77-41C2-9EB5-2BDD4D8AE8DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"745cacc48ae8cb94fb23d08e20c409b0b84fd335","datavalue":{"value":{"entity-type":"item","numeric-id":952442,"id":"Q952442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$260204F1-5846-4594-B9C1-731B705C1FA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c3d962441425809e5a89b92d7cdfde5d540ea32","datavalue":{"value":{"entity-type":"item","numeric-id":3581401,"id":"Q3581401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$5B3557E9-9CB5-4100-A0BE-156A50CBDBD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2da2c70447fa19356e5f62c8fcc8232a8b9790d","datavalue":{"value":{"entity-type":"item","numeric-id":5960737,"id":"Q5960737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$494765A5-1FD4-46C7-A118-1668533342FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65962d5af77abd3313300f4b9fa451755edb61c0","datavalue":{"value":{"entity-type":"item","numeric-id":1121788,"id":"Q1121788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$D43F4069-6C65-4D66-8BCF-3469B76CC7DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76d6092f589b0d6c6dd5e59a4d23b182ee749d66","datavalue":{"value":{"entity-type":"item","numeric-id":932185,"id":"Q932185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$D96FE913-ED8F-4537-A13C-6A35CEDAA460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6855fdd44b075375a63fab37682333a0614f431d","datavalue":{"value":{"entity-type":"item","numeric-id":724056,"id":"Q724056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$7ECCA59C-F6DF-4C4C-878B-760CE964C0F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ac410c9c527a35674b2239d368b8d7ac2d04351","datavalue":{"value":{"entity-type":"item","numeric-id":1728477,"id":"Q1728477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$7E563EE4-FBC4-4BC9-AB24-0E4669E6E9A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"700e5130d886be82e786d087ea9099ea689375e1","datavalue":{"value":{"entity-type":"item","numeric-id":5223754,"id":"Q5223754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$9A8FCA69-55D1-4E40-AEC9-3D43D8AE7563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c35c3c18100f10a76a9ef0d730325b542a65e7","datavalue":{"value":{"entity-type":"item","numeric-id":115238,"id":"Q115238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$198A521F-4812-4640-9FA7-41039B0CEA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"461f4e8c65a424a2e21ba1d0a84d67f6cd7c730d","datavalue":{"value":{"entity-type":"item","numeric-id":2276891,"id":"Q2276891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$9D5DD7CF-EE19-4662-A9FE-FD177A8F9044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9194e9b150f8488fef979658da21ddd0e60751fc","datavalue":{"value":{"entity-type":"item","numeric-id":3651735,"id":"Q3651735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221985$FD3AA32E-ACCE-411C-9E18-5D57ECE9020A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bded2acd3e2df01c05aadcb91f5460e05c897b1","datavalue":{"value":{"entity-type":"item","numeric-id":4648687,"id":"Q4648687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"063f719e889edab45d6104651600ccaf3b4bf25e","datavalue":{"value":{"amount":"+0.8415802717208862","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":"Q2221985$9AB1C0BD-C315-48FE-A8AF-89CE3EFE1F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69b33655396d6490ceea76e5add0a36515712b12","datavalue":{"value":{"entity-type":"item","numeric-id":263164,"id":"Q263164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9c4af49ab07ba7128e9f361a8e0e063ce213dee","datavalue":{"value":{"amount":"+0.8285044431686401","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":"Q2221985$EDB0583D-C5B1-4C48-8FE4-7B21C02CC57C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f75ebbc6831d9f0d0475ef82404b506495f4fb1","datavalue":{"value":{"entity-type":"item","numeric-id":5960737,"id":"Q5960737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b0c98c22a1b8c60deaa1e4c7308103bce2e06c2","datavalue":{"value":{"amount":"+0.8259963393211365","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":"Q2221985$3951883A-555B-443A-8A38-56346F40E731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78e7ac0b6275f112c6482e2b388566257e9a6a34","datavalue":{"value":{"entity-type":"item","numeric-id":1666108,"id":"Q1666108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6709b8946e6bb5462c3e409f2143ebf5d02334db","datavalue":{"value":{"amount":"+0.8188494443893433","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":"Q2221985$447E2158-F27D-4A06-9947-D96ED09196F3","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":"0ef90373d34a3faa7b5848b5694e04bedb3981b2","datavalue":{"value":{"amount":"+0.8175045847892761","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":"Q2221985$112AB944-B906-4C67-B14A-CD8ED6E8B0F0","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":"Q2221985$40BA5C2E-2B56-4A11-B2F5-131DF2D8D355","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2221985","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2221985"}}}}}