{"entities":{"Q1315465":{"pageid":1326215,"ns":120,"title":"Item:Q1315465","lastrevid":68442228,"modified":"2026-04-12T23:44:50Z","type":"item","id":"Q1315465","labels":{"en":{"language":"en","value":"NP-completeness of minimum spanner problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 513347"}},"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":"Q1315465$8E6AC073-1E8A-4754-840F-0031FD39F419","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"117b2b962cf020fd00b940c3557a75ef3fa553af","datavalue":{"value":{"text":"NP-completeness of minimum spanner problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1315465$A846476B-E357-46AD-9E9A-5068662DA610","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47407dea5bc743ac682763279563407320e6f61f","datavalue":{"value":"0788.68057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315465$B2E90AF6-BFF8-420E-83CF-E1877A289B1E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6d7aa1b0eb9b6a26cbac27faaee1be4d11daba35","datavalue":{"value":"10.1016/0166-218X(94)90073-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315465$A7E5FB3D-7CB6-4055-99CF-534A2AEFE39C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f00237d5739b07662cb51e9e957100249e47b2d2","datavalue":{"value":{"entity-type":"item","numeric-id":175508,"id":"Q175508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$C31C9C12-0BF0-4E2B-9EFC-755F836ED73A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$90E306A6-EBEF-4D82-A670-A1890E4409D1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"87ddefd6c83e22cbdb85f95663ace293dcff1d10","datavalue":{"value":{"time":"+1994-03-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1315465$4DB58E6F-DF91-4B3F-A912-9DE3A97E6E41","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315465$79F56440-498C-415B-8A7E-4A625087FADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315465$77881465-2943-4711-A166-2367C9414A6C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cddc717a38217ee20cb0f0de17d84bce6485a77a","datavalue":{"value":"513347","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315465$41BA0375-6341-4996-A89E-3B6F22C5749C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bcb88e4835cfef6b70b1d60481bd40424864103","datavalue":{"value":"spanning subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315465$ACD7AB51-92C4-41EB-871B-145E656AC67B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315465$A7FBA490-FA91-4D71-9816-510D2CAC8262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffa219ea2cff89df5162edb57bd2a31ea73e1a26","datavalue":{"value":"digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315465$176840C9-5441-4910-9694-E1871CD5EE99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"492952222f0a3d8997097bc5e263a894a664b61a","datavalue":{"value":"oriented graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315465$A2A71C13-1915-4202-B034-BEE9459EAB92","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":"Q1315465$D7CF9988-1944-4DE9-9FF7-F4F2732E1A5E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"611d3e7c9668bce11095cc625704a0b304d94a87","datavalue":{"value":{"entity-type":"item","numeric-id":1196368,"id":"Q1196368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$B60A35BF-B8FB-42CC-AA78-BDE51E6EB29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17e3e16f8de4b41a5e87255873ed44ec5fd55e","datavalue":{"value":{"entity-type":"item","numeric-id":3361904,"id":"Q3361904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$0A861DEB-5D53-4B48-B468-E7F468AA2D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3d870108988893b45925715dedf4ad0faaaafe2","datavalue":{"value":{"entity-type":"item","numeric-id":103560,"id":"Q103560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$1421EEF3-98FD-4000-B3CF-65EB5B377046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d45dd5b8ccb621e6aefa5f5d6b3a28b45bc431","datavalue":{"value":{"entity-type":"item","numeric-id":4847362,"id":"Q4847362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$CB89A3A6-81F1-4AF3-BCAB-D1D78ABEB113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ffc7c8b334d26c0686dd1a9b8ac5d7d5836aced","datavalue":{"value":{"entity-type":"item","numeric-id":584279,"id":"Q584279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$24DA54DF-44FF-41DA-AEFD-3EACAE1B8E21","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":"Q1315465$EAB91F5B-79FB-4DE9-AAE1-B42E967F6C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"945c8511c11198e1a76a2127010852a7155b216f","datavalue":{"value":{"entity-type":"item","numeric-id":4312222,"id":"Q4312222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$DDA117A0-04A5-439A-917E-A3AB7521456C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7324ed4dc1f4c24db6af106e66dd1fb972ba579","datavalue":{"value":{"entity-type":"item","numeric-id":5287445,"id":"Q5287445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$09DBC727-BEF7-437F-B9DA-E49A18EDEA31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd94578b97c83ef7077e73a3f78c579ae10dd88b","datavalue":{"value":{"entity-type":"item","numeric-id":3826599,"id":"Q3826599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$7C6CA88E-8ABD-4D0A-9D85-6BED89D60C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f055c449bcd849d79e6dcadb3c541b7ca3a2d18e","datavalue":{"value":{"entity-type":"item","numeric-id":3139291,"id":"Q3139291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315465$D1E788B0-18FF-41EF-AA28-63F938DD845D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"564d7153ec06ac4359a1bf235687ab126101801c","datavalue":{"value":{"entity-type":"item","numeric-id":1784745,"id":"Q1784745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f68208ff5d2bb96564b43fc529a0761b9ea40601","datavalue":{"value":{"amount":"+0.958121","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$618AD6D9-8E06-4832-8E9D-771855483A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1edca5073194ecbade83b3f30e951df4ac19431","datavalue":{"value":{"entity-type":"item","numeric-id":4373672,"id":"Q4373672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d8390682feb39dae7d7f109a75d3b8ceed01366","datavalue":{"value":{"amount":"+0.9520782","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$48D726C8-0681-4F83-8C42-1C2B8664EB56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4b30522581426d8ca8624884b329d3522b5feab","datavalue":{"value":{"entity-type":"item","numeric-id":3836515,"id":"Q3836515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d8390682feb39dae7d7f109a75d3b8ceed01366","datavalue":{"value":{"amount":"+0.9520782","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$A47C1A83-6CCA-41F7-86DA-0A608319DDA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52037fedab33d86780c32374982218ded98652a8","datavalue":{"value":{"entity-type":"item","numeric-id":1199472,"id":"Q1199472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12c0f6e827cb061c6a0b5ed499c0361490d66b20","datavalue":{"value":{"amount":"+0.89608675","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$124A7E9D-4EF4-409F-890B-60C795601A46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ae7c7c8235dcd9029d3c99eab9f79b9fec380a1","datavalue":{"value":{"entity-type":"item","numeric-id":2464336,"id":"Q2464336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92c0b3e20ea349b3a107d07a0ee8c6e6bc200a51","datavalue":{"value":{"amount":"+0.89399636","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$92030AFE-2B6B-40A0-B54E-502842516F0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"910616085cce14bf7444248d022580df36e8aad6","datavalue":{"value":{"entity-type":"item","numeric-id":2728855,"id":"Q2728855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92c0b3e20ea349b3a107d07a0ee8c6e6bc200a51","datavalue":{"value":{"amount":"+0.89399636","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$563472B2-FB8E-4DE3-9FF3-FE9379777690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"086d1d74fc3fcc1f4d367a91f65462e58c5eeab5","datavalue":{"value":{"entity-type":"item","numeric-id":2682929,"id":"Q2682929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cea9b51affe040d3af3ff673de38a12042aa1f2e","datavalue":{"value":{"amount":"+0.88995516","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$42DC4789-CFBD-4C5F-831C-A2EDE0F6F3E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e29594f730aeeea0ebf885e92fbdc20e219e9b60","datavalue":{"value":{"entity-type":"item","numeric-id":1370655,"id":"Q1370655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f6b81f6802b4fda37946f6ff93a072836921de9","datavalue":{"value":{"amount":"+0.8894883","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$2EAB31D0-46DD-4BD8-82C1-74B568B4C949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a13c96e86be9ea7fff7fa8f3f089d79ada92a3f","datavalue":{"value":{"entity-type":"item","numeric-id":2574099,"id":"Q2574099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0086ddcdf3e1f71738fa52a8d79a7653bae4f26e","datavalue":{"value":{"amount":"+0.8832229","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$7ED209F0-20BB-4DB1-91BA-B80E20476A84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6420a92415ccedc0dd8fb23e5ccd283a64e8726","datavalue":{"value":{"entity-type":"item","numeric-id":860400,"id":"Q860400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3b72762e6f82abe5ad9c87f4b3dd5e83569a45f","datavalue":{"value":{"amount":"+0.8753362","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1315465$5CFCC852-2473-4C47-A12C-378501111C81","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"NP-completeness of minimum spanner problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/NP-completeness_of_minimum_spanner_problems"}}}}}