{"entities":{"Q1853118":{"pageid":1863860,"ns":120,"title":"Item:Q1853118","lastrevid":48034138,"modified":"2026-01-03T10:36:00Z","type":"item","id":"Q1853118","labels":{"en":{"language":"en","value":"A note on the minimum label spanning tree."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856462"}},"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":"Q1853118$52CE8BA9-0E2C-437D-8768-B790C5D40E52","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3524e64dbb4ab56acdc8de40e8a2262d87f3329b","datavalue":{"value":{"text":"A note on the minimum label spanning tree.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853118$76272D38-C1F8-46DF-881D-DADF09710F98","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f6051d0086342fcc71b508df4861ca5751075633","datavalue":{"value":"1042.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853118$847A4CD5-D9B5-45E8-8B62-D4ABB674E567","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bed3359302880e4db9dd3f3fff40d012d3637b51","datavalue":{"value":"10.1016/S0020-0190(02)00230-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853118$BB85A83D-4E5A-4419-B4FB-45071EFD075B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46c38a6295874899cc4db80f68afcb2c50d38647","datavalue":{"value":{"entity-type":"item","numeric-id":1850659,"id":"Q1850659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853118$806F49D8-AB05-4F35-AD36-40A3505C1E53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"086fb078700357b2e14dffdc6cc7f31721adb01b","datavalue":{"value":{"entity-type":"item","numeric-id":834979,"id":"Q834979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853118$823AD371-32C0-4E2B-B36A-ABB8D9092A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f7fe40479c00e040397f1228a9a1c528b1efe34f","datavalue":{"value":{"entity-type":"item","numeric-id":1406565,"id":"Q1406565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853118$6315C4AD-2B2E-408B-BDEE-F5518021AA75","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853118$8930423A-38A8-412D-B897-0DFAD4638FB3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853118$180005BA-5F72-4502-BD81-44F7EDF960EE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e0d6b7f87adbee08d507a7a717b2c6e53eaadb5b","datavalue":{"value":"We give a tight analysis of the greedy algorithm introduced by Krumke and Wirth for the minimum label spanning tree problem. The algorithm is shown to be a \\((\\ln(n-1)+1)\\)-approximation for any graph with \\(n\\) nodes \\((n>1),\\) which improves the known performance guarantee \\(2\\ln n+1.\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853118$6F68892F-9A40-4AE6-A890-D4EC9746B61D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853118$C948EBD5-2AAB-4FFB-BC3D-CD06A5B3FB00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853118$D422CDCE-6BDB-47A4-90BC-63AB232036A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca8c16691e9ec83d46a3995338b09d48ac9660ac","datavalue":{"value":"68M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853118$3EF6BF7A-E335-45FC-8DCB-971E4880F505","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ebe65cd231208267c8b4ed44732a763f0c5ec2e4","datavalue":{"value":"1856462","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853118$ED1D2306-5A87-42EF-87BC-17FA36D849D3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eef4348cd3a4d986494cf99e2e2ef5b520d3914e","datavalue":{"value":"Network design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853118$3732A450-50D5-40D0-8CC8-072C7579BAA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853118$AA2DE488-2AC3-425C-A0C9-BD70559DDAC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbff35acdd31439d13dd3892bdda5725c18fc300","datavalue":{"value":"Approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853118$18A0046D-CED8-4E3B-9098-417B3F26A745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"960b36a49bf0d413096fc9c29e9a16d6c3f89da3","datavalue":{"value":"Spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853118$3CC986C0-522F-4D37-A106-F24C27489412","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":"Q1853118$72E7F30D-3285-4C7F-BD28-3A5B223BD76A","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":"Q1853118$6FDD827F-5621-4670-9D9C-571A80E8ABD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853118$0C39F601-5C75-4473-B7FC-6A56CCFFA3DF","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":"Q1853118$1E4F378D-1C89-4F04-95CD-A57201713FA8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3dc348a872f592d5552e84f611e0b4db1f40018e","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(02)00230-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853118$1022B619-7E0E-436E-B85B-7011CDFCBDC1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f3752a68da3b6d68a53c6f6849af0b48c99f5cd6","datavalue":{"value":"W1997809628","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853118$BDB436CA-0004-4A7D-805B-B74F6B44C6BD","rank":"normal"}],"P1643":[{"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":"046c24cc1e54b7856ebd7d6a7dccff7524db0b5f","datavalue":{"value":{"amount":"+0.8831061720848083","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":"Q1853118$03F07A0B-E519-416C-B1E3-37AF14E10C69","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":"6ab5199dc6b7b769082556af0630428c8ae4208e","datavalue":{"value":{"amount":"+0.8483246564865112","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":"Q1853118$79FA6BE0-90ED-4F2E-A8E7-60E989DB67EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd2f28b6a8a544385651b00a3dddb44fe0dcd242","datavalue":{"value":{"entity-type":"item","numeric-id":5756701,"id":"Q5756701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81e161fe43d11f72cf7bd236eb08edbbbdfebe6d","datavalue":{"value":{"amount":"+0.8444185256958008","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":"Q1853118$7FCD557F-7632-40AA-9C99-D811CEFF1F61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53f5c71fe9ec06bf2eb55db21f43202bb45996fb","datavalue":{"value":{"entity-type":"item","numeric-id":1811627,"id":"Q1811627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7cfc5ad96d4a3f95d23f6627e51ff29e5b0223b","datavalue":{"value":{"amount":"+0.8073216676712036","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":"Q1853118$0224C838-B630-43C6-A570-53A3F749A033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"914427bd624654079c2f9c577c0cdccd32718474","datavalue":{"value":{"entity-type":"item","numeric-id":2426652,"id":"Q2426652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d170dab3e0cad219369ba4d537f77d9121eb304e","datavalue":{"value":{"amount":"+0.7979167103767395","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":"Q1853118$2EAA39B4-EA4E-44C4-BED9-03171CD240A7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1853118","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1853118"}}}}}