{"entities":{"Q945943":{"pageid":947791,"ns":120,"title":"Item:Q945943","lastrevid":65540325,"modified":"2026-04-12T03:18:07Z","type":"item","id":"Q945943","labels":{"en":{"language":"en","value":"Computing a minimum-dilation spanning tree is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5345382"}},"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":"Q945943$D1AB6DFD-CD51-4745-A175-AE9D67C12700","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"51e657fdbeaf74cb2342b32157b77509ef33a30e","datavalue":{"value":{"text":"Computing a minimum-dilation spanning tree is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q945943$7E6FFB5E-9971-406D-AAA2-2C02E6CDEE23","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c03be5333c2696149904f0a05b86b30821d18751","datavalue":{"value":"1188.65018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q945943$02EFC7DC-6E52-4E0D-B4C7-03E80BBEF121","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$78FA4CAC-A9C0-47F3-A6E3-48D9A79680B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8fea402372c91bc6391451417dd65399c391428a","datavalue":{"value":{"time":"+2008-09-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q945943$C4651898-67B7-4C74-A426-8C0783EF77B5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q945943$11673061-6619-496B-97DC-D9E391C48C89","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"82770256c9bb726d2cfd47cdfdb8a5537a11d81d","datavalue":{"value":"5345382","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q945943$B4A45F70-E59A-4704-A1F0-84613E142BF5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24967c4c0a3e418fabd43fc2e5041c3116fe774b","datavalue":{"value":"spanner","type":"string"},"datatype":"string"},"type":"statement","id":"Q945943$A4CCCE78-9F0B-45AC-A039-04CC5EA46EEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ada8d30f2ef08fc8cb2c5d1f7da969abbc27918a","datavalue":{"value":"dilation","type":"string"},"datatype":"string"},"type":"statement","id":"Q945943$4D7C42AD-A087-41E0-B24D-E324379E84B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c27024bc3112e6fbf1cca0a9a4aacb8e7e4a77e0","datavalue":{"value":"optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q945943$07C7CDA9-B62D-48BC-87F1-C9BBEE12082D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q945943$2C21AECA-DDB9-4D2B-A545-70B359952266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"695a508ed3c8d6131b66c6dd2524d8f0ec95e4ed","datavalue":{"value":"geometric network","type":"string"},"datatype":"string"},"type":"statement","id":"Q945943$1144699F-D275-4225-A172-D5762A114F3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q945943$0FCB419A-0F82-400D-8864-FAF04D95E628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f85e9f2721221f48af2e899508349c71e3faa29f","datavalue":{"value":"shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q945943$88F5CA7C-E101-4D93-B9CD-73502F52FB50","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe51ab34fca76d52c385a1ca93b7dc29b1c6d1a2","datavalue":{"value":{"entity-type":"item","numeric-id":1175645,"id":"Q1175645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$F0C9B157-8D1E-48B8-B694-00E2D1606C6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2dbac174e7bb882624e2642be18b7dd92f382daa","datavalue":{"value":{"entity-type":"item","numeric-id":1776900,"id":"Q1776900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$3D0085CD-BD7D-4F50-A465-8C5CC34571D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4910a5176f388d52e02d812b972dbfc75c619ead","datavalue":{"value":{"entity-type":"item","numeric-id":2236854,"id":"Q2236854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$21FFFC66-8527-42D0-9EA6-012FAE597058","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":"Q945943$449298ED-7D98-46DF-9794-39175C06B391","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5bcaaf954600e2d371f84e4708628afeb66259fb","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2007.12.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q945943$3EBD98E7-A500-4475-9824-CF908271CCDB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"297ec2c7de0b50f8a306b76aba5772e7b5ef5d54","datavalue":{"value":"W2065889331","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q945943$F3877E0A-2792-440E-810F-84C0E5F7C07D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62fc2e8b26fdc2fec2f73875e5c47de2ea29e38","datavalue":{"value":{"entity-type":"item","numeric-id":929746,"id":"Q929746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$B4FD0A2D-D3E4-4D48-A367-6EB6997FFDA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"134bb2199c5f93c9b1f6f9a5ea427a220f4cd3d2","datavalue":{"value":{"entity-type":"item","numeric-id":4886312,"id":"Q4886312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$2F0EC41E-BBD6-4BEC-A661-7A6030EDC27B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60823dfccc4e3f3a4b3977f2a4d0dcb880104c9c","datavalue":{"value":{"entity-type":"item","numeric-id":4945509,"id":"Q4945509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$EC5D7837-589B-4225-BF71-EAD04584B39C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cc1ac9913cb4b5ee0d5d33f24932900890eb1b6","datavalue":{"value":{"entity-type":"item","numeric-id":5475865,"id":"Q5475865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$B763B0BC-0B37-4B2B-A7C0-E929C6EA4BE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f54afa2a3485ddcdc52058e1321b340acec88d76","datavalue":{"value":{"entity-type":"item","numeric-id":5928870,"id":"Q5928870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$88A1C9CC-0006-4BC4-8977-5A506A8297BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faa28c0d9a84d5fd59de0084cfb6c3d02cc24520","datavalue":{"value":{"entity-type":"item","numeric-id":3595495,"id":"Q3595495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$67DCD2DB-4A2C-4D29-A33E-48CA81D2526F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64c4571ef8850cc0ee90e898ddf88f25456c0ebb","datavalue":{"value":{"entity-type":"item","numeric-id":1194346,"id":"Q1194346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$BEE8752F-05BA-4C8E-9215-68D49565FBEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa11d25f10ba7b51ba728b6bc864da2f4f475c36","datavalue":{"value":{"entity-type":"item","numeric-id":3986395,"id":"Q3986395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$36F63738-0A13-4E58-92DE-44657444A32E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3ce1070a6a96e7ecec830fcc7251e1c184037b1","datavalue":{"value":{"entity-type":"item","numeric-id":4945521,"id":"Q4945521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$F522E5AF-5B9D-4373-AF1F-35331C7E5889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"404e2f0e861f0a7cb0f69a7c8bd6960d2eebff06","datavalue":{"value":{"entity-type":"item","numeric-id":1814131,"id":"Q1814131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q945943$A41D3CD2-083B-4E40-8FC3-6E3C6ED0C4B0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"93892a53d0f424653ef9025a30faf59d7e14afc8","datavalue":{"value":"10.1016/J.COMGEO.2007.12.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q945943$2018C138-B538-4232-A979-E9CAAC5EEF8C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e85f212cebe6b21ea946264d747933e105e3b70f","datavalue":{"value":{"entity-type":"item","numeric-id":3595495,"id":"Q3595495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09f7c4a18128a16acc0c09651a512a10f3d0d9f6","datavalue":{"value":{"amount":"+0.927920937538147","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":"Q945943$173A8BAD-99F7-4511-B7A5-3C1AF51FA927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98d6d35fa2f2557a24e677266804bffeec977936","datavalue":{"value":{"entity-type":"item","numeric-id":3562852,"id":"Q3562852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b613a145a02ad68da49c955b9bdd1af46accc09c","datavalue":{"value":{"amount":"+0.9158405661582948","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":"Q945943$44FD7A46-4BB5-440A-BB7C-488A1A74B870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc37b493115cdc279ba187ad8d507a4f70e49cd4","datavalue":{"value":{"entity-type":"item","numeric-id":3196394,"id":"Q3196394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1819e976b157ebc38b794c64dd232cf31f30e1c8","datavalue":{"value":{"amount":"+0.8574001789093018","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":"Q945943$0DD36FD6-AF9A-468C-8F1D-4D42B5986664","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b9273c36fbdda97a7681c2ed00324adb5a9bde0","datavalue":{"value":{"entity-type":"item","numeric-id":3459364,"id":"Q3459364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52be758120ae9bbc33259c6b1210acc0f671d6cd","datavalue":{"value":{"amount":"+0.8409775495529175","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":"Q945943$2E9BF8B0-20C0-48D4-B143-9DC80FBE565E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc51925057d21b1568c4114e62dce7c39405604c","datavalue":{"value":{"entity-type":"item","numeric-id":1920421,"id":"Q1920421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7254657cd0385d7104b55fb3caf69e78f3bb8cf8","datavalue":{"value":{"amount":"+0.8252299427986145","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":"Q945943$9EF0163B-86DF-49CA-8DF1-9500643F4D1E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing a minimum-dilation spanning tree is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_a_minimum-dilation_spanning_tree_is_NP-hard"}}}}}