{"entities":{"Q2682929":{"pageid":2693672,"ns":120,"title":"Item:Q2682929","lastrevid":47808766,"modified":"2026-01-02T18:17:40Z","type":"item","id":"Q2682929","labels":{"en":{"language":"en","value":"Improved NP-hardness results for the minimum \\(t\\)-spanner problem on bounded-degree graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7648690"}},"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":"Q2682929$3563B9BC-C4BA-4474-A1DB-C25D87DD3A15","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"28b130c9dc86722cd3780638d7d60e63eecff24e","datavalue":{"value":{"text":"Improved NP-hardness results for the minimum \\(t\\)-spanner problem on bounded-degree graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2682929$0BA66C13-F4C0-4B7D-9243-35D0CCC4DBD0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ed9dfee842df23fe51adb9113781f90c56ea3634","datavalue":{"value":{"entity-type":"item","numeric-id":1627173,"id":"Q1627173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$8F99F525-4741-413B-A749-A9497B805167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"03c0c85681c77cd7b0eca819a5dde886cd585b85","datavalue":{"value":{"entity-type":"item","numeric-id":251068,"id":"Q251068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$45806756-0AD0-4BED-B21B-65ECA1FFAC8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00dcd34d2a42ffd4c9646545f08dca80da5e12dd","datavalue":{"value":{"entity-type":"item","numeric-id":590171,"id":"Q590171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$B9E66D46-71C8-438E-9331-E11FA127620D","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":"Q2682929$1A2B116D-F895-45AA-BF96-8C6A7E7EBD30","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2c8e339b7d8e23c2957c5b00a51a7fa7180b9d1f","datavalue":{"value":{"time":"+2023-02-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2682929$67BE2449-0999-4F05-9CC6-1DFE6EACCBBF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2682929$3C23A2AF-35E3-44C4-9EA4-B96DDE9234D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e92287d1011c7dddc18f093d9f0e9b781f473d77","datavalue":{"value":"7648690","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2682929$FBB93D58-0CCD-491B-8516-C892A3D1E2CA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24967c4c0a3e418fabd43fc2e5041c3116fe774b","datavalue":{"value":"spanner","type":"string"},"datatype":"string"},"type":"statement","id":"Q2682929$015BD898-D6A9-4833-A111-FF80BB3E4492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"438b7ecc04a18a73e72a8f20222e422ef0b81da2","datavalue":{"value":"sparse spanner","type":"string"},"datatype":"string"},"type":"statement","id":"Q2682929$B8AFF596-DE7B-4A91-A855-AC586CDEF17C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"150f00e58285deae2fc652f4e8bba3f3fe4f22a3","datavalue":{"value":"bounded-degree graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2682929$A49A4FBA-CC8E-468A-96F9-6DF676066B53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2682929$DA7E68C8-8C7D-44F1-9433-4F5B10C08C6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36298a4b85de9b87ac53ecd8de1581c13ad52627","datavalue":{"value":"\\textit{NP}-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2682929$9E83C977-E8FE-4982-8CF5-7C73D9DA421D","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":"Q2682929$68BAC4CF-C90C-45E4-B7A2-5E1B849AE460","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d535c66af089f0bce9bdda2f2754017d2bf167c9","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2023.113691","type":"string"},"datatype":"url"},"type":"statement","id":"Q2682929$E3864B1D-3E21-400C-8FC5-BFBD52353477","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"923472f27485c27d6444aa91989f875ba6d8aa73","datavalue":{"value":"W4313893408","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2682929$76B45FE0-1722-4784-A2EC-E5B0BC8CFD8B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5816b6dd58ebbb5e79873a7664c2115f576c4e71","datavalue":{"value":{"entity-type":"item","numeric-id":2026289,"id":"Q2026289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$5E93D403-B35B-4848-AABB-0615DE543DEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5d048233381c0716ea6c30d78f1c09dc6fb64e9","datavalue":{"value":{"entity-type":"item","numeric-id":3765248,"id":"Q3765248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$F81EB11D-2456-449B-B5B0-9DB2A01D7735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19dd55cf13392268fd42a9a26b797013949c1518","datavalue":{"value":{"entity-type":"item","numeric-id":2944530,"id":"Q2944530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$80938A7E-A932-4C35-8B62-62376916CA89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$19A16A5C-DB38-4AE9-B167-0ACFF1A7EFF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7746f9c2a7f4f7cf358505c4e745e933275945e","datavalue":{"value":{"entity-type":"item","numeric-id":4228290,"id":"Q4228290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$98EC3A7B-365B-40CA-A8FD-2408520FC435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20e39ebb0cf7a6192de190b00737fcbf9823edc1","datavalue":{"value":{"entity-type":"item","numeric-id":868437,"id":"Q868437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$6576B754-BFA7-459D-A715-56316F0CA0D9","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":"Q2682929$C2AFD076-7DD9-4F28-92D4-24F1A7620CEA","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":"Q2682929$F51C29F9-C6BB-46E5-BB7B-9518516D8220","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":"Q2682929$5DB1FA8F-878C-43C2-B1D1-D2CAAE630053","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":"Q2682929$817CEBC3-C16C-4F26-BAD9-367069409CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fac8750c6e7b109dbf3fefc470156c6889865f2","datavalue":{"value":{"entity-type":"item","numeric-id":2154116,"id":"Q2154116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$54BFF514-19A0-42F3-B5A7-B3EB73B763CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f0c61cac4ba687040b7673c10b1d12dca785cd1","datavalue":{"value":{"entity-type":"item","numeric-id":1784745,"id":"Q1784745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2682929$95747B60-7D2A-4C2B-A2E4-FE7273A4867D","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":"Q2682929$5DD7E107-9704-4A95-9F2E-1F29FD06A500","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":"Q2682929$E1EC9222-AB0D-4CF1-AB98-E1D7E0F4A296","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":"Q2682929$D4F9BAD9-EEF2-486D-8F3A-7E7F4940018F","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":"Q2682929$D145D71D-3364-447F-9ECC-6BCDEE079D2A","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":"Q2682929$287EF080-1578-4B7D-B712-90DA149D95A5","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":"Q2682929$F3385427-413B-42F5-9774-C932605F77C4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7c2197ba32598b7af99d6bc7b6b41eba00b2d73f","datavalue":{"value":"10.1016/J.TCS.2023.113691","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2682929$16674261-337C-4C3B-901F-FB163E3898F7","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":"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":"Q2682929$A0D3CFD3-5054-4A50-9CBD-B1A9F1EEA987","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":"0093d3e95b62bee4cd89642d2235774ab66c78f8","datavalue":{"value":{"amount":"+0.902018904685974","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":"Q2682929$944465E5-154F-40F8-AE5B-B9CFF2A4953F","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":"2ab2acf545f638b8d59642b289629df9260d8809","datavalue":{"value":{"amount":"+0.8956912159919739","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":"Q2682929$9305FB1E-1AD2-4015-BF33-E2D3C832CE86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc200a0e6ba4e539493178ffeec63736bd2f165c","datavalue":{"value":{"entity-type":"item","numeric-id":3620618,"id":"Q3620618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffbfbf53b05caa716cb8b541cdf6a87222669f58","datavalue":{"value":{"amount":"+0.8953356146812439","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":"Q2682929$99665DEB-461F-44B9-A473-E55DE8459986","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":"4c7875d60c833326a4e48e299866a65635d676ff","datavalue":{"value":{"amount":"+0.8668996691703796","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":"Q2682929$1F2246BB-2781-4650-8008-6011FB430D0D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2682929","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2682929"}}}}}