{"entities":{"Q666399":{"pageid":668248,"ns":120,"title":"Item:Q666399","lastrevid":63637758,"modified":"2026-04-11T14:31:21Z","type":"item","id":"Q666399","labels":{"en":{"language":"en","value":"Solving the minimum label spanning tree problem by mathematical programming techniques"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6013006"}},"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":"Q666399$55B383B9-1A5E-4175-996C-67A09D59870A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"81fce5c6232ead1db1bc8191ab1a71877e2f81cf","datavalue":{"value":{"text":"Solving the minimum label spanning tree problem by mathematical programming techniques","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q666399$3F1C80A1-24E0-46C9-82DA-06912E70749D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"76e6cb360d47c9aee743a64537321fb8cf8ebcb8","datavalue":{"value":"1236.90134","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666399$D2210811-EEA0-4A8A-8EAB-E22891CF56EE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f9208a2e5bf902fa2ec43db0d23ff18f68bf8c98","datavalue":{"value":"10.1155/2011/143732","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666399$745FE877-EB18-4229-AFA4-E2225ECD74D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f4dd8ec5767ce64439eaa9f8284398517918d9a9","datavalue":{"value":{"entity-type":"item","numeric-id":666398,"id":"Q666398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$5CB441C4-7907-45DB-B17E-CAEB2A14920C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1b2829afa6e2e13342a35abb3f606a91ed083e7f","datavalue":{"value":{"entity-type":"item","numeric-id":248083,"id":"Q248083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$797A1DA8-321C-4459-A3A6-BA223670FD76","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"76a9d9a0baf762804f757cc839f33fba5b98847b","datavalue":{"value":{"entity-type":"item","numeric-id":447553,"id":"Q447553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$04C8292E-1EC5-4BCD-9983-835D730210AC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"086baaac6cfff2b3761aa8ffbeed776449d2b918","datavalue":{"value":{"time":"+2012-03-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q666399$00E52568-5CBB-44A9-9FC2-8650759DA712","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"162cdf0832c0aec216a53fb122495f166e0f8a48","datavalue":{"value":"Summary: We present exact mixed integer programming approaches including branch-and-cut and branch-and-cut-and-price for the minimum label spanning tree problem as well as a variant of it having multiple labels assigned to each edge. We compare formulations based on network flows and directed connectivity cuts. Further, we show how to use odd-hole inequalities and additional inequalities to strengthen the formulation. Label variables can be added dynamically to the model in the pricing step. Primal heuristics are incorporated into the framework to speed up the overall solution process. After a polyhedral comparison of the involved formulations, comprehensive computational experiments are presented in order to compare and evaluate the underlying formulations and the particular algorithmic building blocks of the overall branch-and-cut- (and-price) framework.","type":"string"},"datatype":"string"},"type":"statement","id":"Q666399$54E29579-57D1-4DCE-AD51-81D0307616EB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666399$25721643-23FA-493C-91D3-F9C73139E399","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf44f3ad3a2f88c9b2a45e4395030d611f0589bf","datavalue":{"value":"90C11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666399$C660AE6E-77AD-421A-BBBF-B01D48926DCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666399$AECCD6E9-DAC9-44ED-955C-9ED8EDC282BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7b0f78b1d7110d7c221278f61117b7633bc1259d","datavalue":{"value":"6013006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666399$9ED4A6CF-9C06-41CD-A5AD-955CE67E2AB6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec16471d667d295403e4eb313d13a0e5ec43ce29","datavalue":{"value":"minimum label spanning tree problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q666399$1195F75E-B124-4394-846C-9791AEE0E981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ad0d3b6cc1f46dc5bad236d53b046e70ce7f7a2","datavalue":{"value":"odd-hole inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q666399$33527B07-1FC8-4858-88CA-FB9E15187A10","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"6663be921a3fe3b244879abf2c0c98e00d21e962","datavalue":{"value":{"entity-type":"item","numeric-id":13835,"id":"Q13835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$8B4CF7B2-469A-4059-B501-28CEF63630B9","rank":"normal"},{"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":"Q666399$7438EDEC-A921-4D69-9DD8-32887ADB7F5E","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":"Q666399$2F285B7C-0C69-493A-B176-3FEDE1E6DCCE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d101bdb2b2e36e40d26d40677b09a473e2eaed72","datavalue":{"value":"https://doi.org/10.1155/2011/143732","type":"string"},"datatype":"url"},"type":"statement","id":"Q666399$6DD02FA4-7308-4CE5-996D-DE1AC3B6023E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"98691a88268f3b69e1885430dfcdf0ca71f657c3","datavalue":{"value":"W2001366300","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666399$4DC95D0B-326F-43BE-B63B-50A42A08C76E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"56cecfdf12732aa9a47866c8f675595c8fca2284","datavalue":{"value":"Q58655016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666399$4AB3FF2F-E9A2-4CC7-A24E-15047B8C8598","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"caea1b9fae3c73230a03a25384422c4d9ad2d79c","datavalue":{"value":{"entity-type":"item","numeric-id":1567492,"id":"Q1567492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$83C097F3-8D03-4B7A-B857-A1D5F3D0BFEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5aaee5a7eb4380e24bf784b751d7633c396083f","datavalue":{"value":{"entity-type":"item","numeric-id":1567494,"id":"Q1567494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$65B59519-FE40-439B-95AB-5DB3A179602B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81ad59edd83c5a5922888485314cbd43fe65f847","datavalue":{"value":{"entity-type":"item","numeric-id":1853118,"id":"Q1853118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$FFECF14F-78E1-47D2-AE6C-C9FDBE743493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf5f4f2ac7337f347b05e6f02010b79acb6115e","datavalue":{"value":{"entity-type":"item","numeric-id":1886801,"id":"Q1886801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$36D98F5E-BEBA-4802-8F6E-632B55F8362D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a870028e8258aa2ea2f8d9afece3b41f26b735a","datavalue":{"value":{"entity-type":"item","numeric-id":1811627,"id":"Q1811627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$7ADC876A-B517-42D3-B66A-C54103F790A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"640b72eb053c45b99323f926c815271ac5bdb17b","datavalue":{"value":{"entity-type":"item","numeric-id":1027523,"id":"Q1027523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$BEA99802-E450-47F7-A6D9-BFEFCDBA7098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b13a86824d5263d39f38c5b2cdacfb00accbea9","datavalue":{"value":{"entity-type":"item","numeric-id":2267296,"id":"Q2267296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$1CA809BE-D502-4C21-92A2-571BCCE37F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e1d3188fc828f3f1730fde41619946413af800","datavalue":{"value":{"entity-type":"item","numeric-id":1025265,"id":"Q1025265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$5A38CF10-E38D-4617-B5E3-4D55C84E8D35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03640f3efdc2b2d53c781c73edc5093f9b69d393","datavalue":{"value":{"entity-type":"item","numeric-id":846172,"id":"Q846172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$64C3CBBF-C837-435D-B971-9119D4809FC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bcd935a5b8d2b98c3e577acbefcd660095c66bc","datavalue":{"value":{"entity-type":"item","numeric-id":4943600,"id":"Q4943600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$FC341CBB-8C07-46D3-A25E-8838C3DE8722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007e3e3da358c5c2f6c0ac26a316656a1143d5d8","datavalue":{"value":{"entity-type":"item","numeric-id":4845371,"id":"Q4845371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$EDAA78DA-3DDC-48E3-AEE0-85A0BFC3BC11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd5010d10a4a78bf20ab3ae25b949eaeadf32e38","datavalue":{"value":{"entity-type":"item","numeric-id":5406206,"id":"Q5406206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$7737A491-DCE0-4EB8-8D06-FAB022851863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cdc8ab92d92234a6c60e69beca185042cc554d5","datavalue":{"value":{"entity-type":"item","numeric-id":3281501,"id":"Q3281501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$B479F51B-811F-4BDD-A0DF-5D3DAF97E04C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5036e4b1ac3c0bcc766679cf51fa757d2c361848","datavalue":{"value":{"entity-type":"item","numeric-id":1386767,"id":"Q1386767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$C8FC7569-BF94-4418-9B9A-FE922250FC99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9613f02474828b8daaa32e2e009f4f9551b86dd1","datavalue":{"value":{"entity-type":"item","numeric-id":1122477,"id":"Q1122477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$53EE66E7-2F93-4E7C-BECF-F9DC9964835E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82fec6e580bc1a1c6b85af965d03783746bfb4ef","datavalue":{"value":{"entity-type":"item","numeric-id":3703653,"id":"Q3703653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666399$01ACAF70-44B6-4FE0-8557-009C4F12F281","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12308edfb65feac09dd91a08d1980b0b2f58dae4","datavalue":{"value":{"entity-type":"item","numeric-id":1025265,"id":"Q1025265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3befe33c61e97c6123619f859e23626cb058ad1e","datavalue":{"value":{"amount":"+0.8487587571144104","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":"Q666399$D03C10B1-E631-489A-8112-D64C4BE61003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ee327ef990531a74bba8bdfd5ab07843034b59f","datavalue":{"value":{"entity-type":"item","numeric-id":2329708,"id":"Q2329708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86778c2f3326ba7682b8af0aea0ab41d188da2ce","datavalue":{"value":{"amount":"+0.8082659840583801","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":"Q666399$16D991A6-E181-4446-98FF-2FB11FA7710A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77f4cfe3a4b0d832e5bc81ea9e7ceb7acdbb5951","datavalue":{"value":{"entity-type":"item","numeric-id":1567492,"id":"Q1567492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9e37cd514b896b2899dcd96237bc6ce1b0707f4","datavalue":{"value":{"amount":"+0.7984237670898438","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":"Q666399$FCF0AC55-BFFD-47FA-ACF0-6EE2188EB4BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77cf0f97e10e3672546b9c4d636f505170203657","datavalue":{"value":{"entity-type":"item","numeric-id":1567494,"id":"Q1567494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec44d574b0c893c8687eed7058c09a67c8d15d2c","datavalue":{"value":{"amount":"+0.7929511070251465","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":"Q666399$4F0FF971-809B-400D-9EB2-D755BAAE4945","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbbb6b90b7d7a1c93bc420d91dc731c0561b45db","datavalue":{"value":{"entity-type":"item","numeric-id":6162004,"id":"Q6162004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93769e61219caf395b9d0b14b2536ed3ad098d53","datavalue":{"value":{"amount":"+0.7921200394630432","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":"Q666399$98B72B47-5206-4094-A09C-EF78AD2ABFA7","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":"Q666399$D8DF84AA-A96A-4613-AE62-AAE0D6849058","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solving the minimum label spanning tree problem by mathematical programming techniques","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Solving_the_minimum_label_spanning_tree_problem_by_mathematical_programming_techniques"}}}}}