{"entities":{"Q1784745":{"pageid":1795487,"ns":120,"title":"Item:Q1784745","lastrevid":53214008,"modified":"2026-01-24T11:46:35Z","type":"item","id":"Q1784745","labels":{"en":{"language":"en","value":"NP-hardness and fixed-parameter tractability of the minimum spanner problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6944702"}},"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":"Q1784745$A8A606C8-45F5-4182-8BB5-18B938804409","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e872fe2e8c0a753a88c86a8890402e653751c2c2","datavalue":{"value":{"text":"NP-hardness and fixed-parameter tractability of the minimum spanner problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1784745$08D1CE3B-EDAC-4E90-A9D2-A005A9E885C0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1a66fd4078e135a4676b826c41fbb468dc678e85","datavalue":{"value":"1401.68098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1784745$747EE150-B552-427C-9E95-E39F63D3A0E8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd4984510ecb87e1198d778e5c81672940646bc6","datavalue":{"value":{"entity-type":"item","numeric-id":273162,"id":"Q273162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$30A39825-8F28-4AE9-918E-9B6081573084","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$64009903-7A26-4B88-9A0B-AAF58EA12387","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7fafee86c1e45e0bcaa02c3657a70c764319b69c","datavalue":{"value":{"time":"+2018-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1784745$6647A95C-8A8C-4228-88AC-C7FF92075595","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4386c7a6627d794773b55f029ac14c950fb0436a","datavalue":{"value":"http://hdl.handle.net/2433/244837","type":"string"},"datatype":"url"},"type":"statement","id":"Q1784745$23BB3C73-DAF9-490E-BB1A-92D064B82B98","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1784745$F598C853-F721-46D3-8F2D-CE53497E8C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1784745$1B8470A5-533D-4B8D-83CA-CF96D4C45A77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1784745$4B9A53C2-6141-4C09-A6AE-F8B535DB479B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"40750fb3664594a1ab5cf63c500213fd07045321","datavalue":{"value":"6944702","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1784745$C76C25B7-4A95-4AEA-B160-E52327CB012C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdae9ec02f4ab3d21a07a0929917bf1a5b3c4780","datavalue":{"value":"minimum spanner problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1784745$1E6F4F1F-F1D2-4ADB-A186-BC094EC3690A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1784745$1FBA9DDA-18A9-4A3C-A0FB-D67B6B93B292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cd1d18f1fee5ae59fc27efa729b5a5f5809add9","datavalue":{"value":"degree-bounded graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1784745$25878EC9-BD72-4557-BFC0-894571B20903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1784745$12D22BF2-08E4-47B5-8890-21AA0009EB41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21385f5218bfc8a686c54ba2c886106c125eec15","datavalue":{"value":"FPT algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1784745$DA4647C1-5FC2-4BD3-ABE6-C830DB585CC9","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":"Q1784745$7E70BBF0-25F3-4B67-A2ED-0FF8DF6BD5EF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a781762932a4dcb47bed2c1063a5e05d1c25244","datavalue":{"value":"W2810702411","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1784745$B219C8FD-3AC7-4F3B-8685-0D80DED7438B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9f50e61488397ba86684892de27d36b83d506ce","datavalue":{"value":{"entity-type":"item","numeric-id":4640279,"id":"Q4640279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$E2CAA280-448E-469A-A4DE-39B898C0E775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddeec664ae5f2c605bc40b1b32c543a8af88ee10","datavalue":{"value":{"entity-type":"item","numeric-id":4373672,"id":"Q4373672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$4E18EEFF-568A-4626-AB52-01CA54BB3BB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0942b7eb9cd2fbcc3749cd648795867620d0ffda","datavalue":{"value":{"entity-type":"item","numeric-id":1315465,"id":"Q1315465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$1754234F-CFAD-4D05-89ED-8C5A9044B8B0","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":"Q1784745$964ED7CC-BBC1-4261-A2BE-63E2C8F6E581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf9843c301db572363891c79a46b27d4571a332e","datavalue":{"value":{"entity-type":"item","numeric-id":4303628,"id":"Q4303628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$26F95213-57E9-408C-85A5-89FD3D0DBD45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bbb00cb242018cdf798a0e6ad4a3f526229b4f5","datavalue":{"value":{"entity-type":"item","numeric-id":5741744,"id":"Q5741744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$80106D66-D2B7-4714-A841-9F94D03377A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cdc19754ceeb9cd362d32e700f6f226495040fa","datavalue":{"value":{"entity-type":"item","numeric-id":4575642,"id":"Q4575642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$B73DADF6-A736-488C-B4D0-A572710BA943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9562975b659ee36323bc10f44914f734dbe22ea7","datavalue":{"value":{"entity-type":"item","numeric-id":4210144,"id":"Q4210144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$C78CE479-0DCC-4E55-BA2E-16F87D03F005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd76a4a23fd717f0882a13aa86a7f9be30dc49a3","datavalue":{"value":{"entity-type":"item","numeric-id":4406310,"id":"Q4406310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$48BAEEB0-3ACD-4830-9931-71DBFFB510AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5af155c696aeb662bdc9d0da98fa78f3509098","datavalue":{"value":{"entity-type":"item","numeric-id":4819695,"id":"Q4819695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$5ACA6578-A029-4AA7-80B0-F50BF4126137","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62e967816953cecad41268e715794a55d56323d","datavalue":{"value":{"entity-type":"item","numeric-id":3577833,"id":"Q3577833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$627748CE-7041-40D7-8F4F-2A24318C993C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6dfd0e4e8118d4d05c83064778e7837a479e598","datavalue":{"value":{"entity-type":"item","numeric-id":876695,"id":"Q876695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$C3861B3E-29C1-4340-86EF-14421D4DB80E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b36a6310d0cc4d46ce55e0a998abce80214928d2","datavalue":{"value":{"entity-type":"item","numeric-id":5892152,"id":"Q5892152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$4E37C50F-C302-476D-BE33-580C6E1A0524","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":"Q1784745$DE9428A2-04D1-41D9-9FFA-D19CFBA0413B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5d72c063db7d4a60c349c83b4d60f54ad52bcb5","datavalue":{"value":{"entity-type":"item","numeric-id":671393,"id":"Q671393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$96AC5656-1622-4254-A6F2-5E31AD962C9A","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":"Q1784745$2D9F6BF4-2944-4231-B468-CBDD887E43FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b808bb57740e05faa3e8a9c198630a5e8fb4cce4","datavalue":{"value":{"entity-type":"item","numeric-id":4730798,"id":"Q4730798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$13CA6658-C57C-47C3-8365-A18ED6D79AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab04252171046432b6c8e826a129af021d1a1849","datavalue":{"value":{"entity-type":"item","numeric-id":4710684,"id":"Q4710684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$8DBDBF41-5A69-427B-B8E2-0852F4462F28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f8a5087e5adfec5e35350c9dc4814ad45a304d","datavalue":{"value":{"entity-type":"item","numeric-id":3546311,"id":"Q3546311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$6194A5B4-7C6A-467D-A1F9-625779D6D669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"400a442b0e01d0ceb7c028e150530bf84c3a7dff","datavalue":{"value":{"entity-type":"item","numeric-id":1370655,"id":"Q1370655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1784745$2AEA3DB9-B8FE-4AAC-8D09-CF31B68AD382","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"98a663bea403a5cd1db8c4fb8b409e095b66c542","datavalue":{"value":"10.1016/J.TCS.2018.06.031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1784745$0982796F-FE0C-4C47-BF75-A696A6B600A0","rank":"normal"}],"P1643":[{"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":"ee88b60eb31a54fefe0443ab3589f56903856b0e","datavalue":{"value":{"amount":"+0.9325718879699708","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":"Q1784745$0A2E5725-F517-4D58-93BE-C2C1DF20213B","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":"24eee08980d8742cec1ab6d17de7af9b6b33939d","datavalue":{"value":{"amount":"+0.9231448173522948","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":"Q1784745$B6474DAE-E5B8-47CD-B184-DCCD70AC0E27","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":"5390d753c147c953d42e59dcb859eac4080cea55","datavalue":{"value":{"amount":"+0.8949616551399231","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":"Q1784745$6799D1CB-D11D-45BE-980C-EF8C043A4DA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e39269e9f18e9370fe279a3b9d6488a275760838","datavalue":{"value":{"entity-type":"item","numeric-id":5928870,"id":"Q5928870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cae15d305acb6035ea12398f761c275ad2774e3","datavalue":{"value":{"amount":"+0.8921308517456055","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":"Q1784745$8C81EAA8-4376-4FE5-9019-67C1BA18D239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"831e2b7a6673bae873b8e2ec7b8826d59fca7426","datavalue":{"value":{"entity-type":"item","numeric-id":1315465,"id":"Q1315465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b60fd9c118e67fcc4968a107f53069d31e59149","datavalue":{"value":{"amount":"+0.8759840130805969","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":"Q1784745$7B5FCA82-D094-4C37-94AC-659885C9541D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1784745","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1784745"}}}}}