{"entities":{"Q2883542":{"pageid":2894267,"ns":120,"title":"Item:Q2883542","lastrevid":42441747,"modified":"2025-06-27T18:47:32Z","type":"item","id":"Q2883542","labels":{"en":{"language":"en","value":"md-MST is NP-hard for \\(d\\geq 3\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6033901"}},"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":"Q2883542$1E42DECE-B200-4468-9FE9-3BD5B31A6438","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61eed236d6795d15fc71df303dbcbe96c4a6f2be","datavalue":{"value":"1237.90270","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2883542$F69882B7-90F0-4659-B8CF-27F3278C37CA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1dc0fbf0ed1e2c988739328e4e4bfcc34a06b0b","datavalue":{"value":{"entity-type":"item","numeric-id":976014,"id":"Q976014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2883542$EB65B97E-E011-42E7-9A7C-AC53C65DE819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"09cee21f93a05b937de9f3fec651bc43611088e4","datavalue":{"value":{"entity-type":"item","numeric-id":869012,"id":"Q869012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2883542$7B665B58-B00C-42FE-B9D7-48631B96D919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4c6afb21eabc3cd675f882b913672e0779fd8ee0","datavalue":{"value":{"entity-type":"item","numeric-id":1348251,"id":"Q1348251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2883542$AB88A340-917F-4D9A-81B6-B841D01593F7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a136d04e761e9859ba9ed38b65864112febfa028","datavalue":{"value":{"entity-type":"item","numeric-id":111211,"id":"Q111211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2883542$258F4C88-2FAD-4E63-A3EF-6D8AB83ABB25","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"43d88f7d78ed551eaafdba0e8b65f63e3ea90e6c","datavalue":{"value":{"time":"+2012-05-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2883542$501008A6-78D2-46D5-A498-23111662EBE7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2883542$2B500451-8FEF-4E2F-8D76-E18A4E2A212E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2883542$DCE635F0-A414-40D2-8FBA-BC827E39E6B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2883542$78B05CCD-0E93-4AD9-AEEB-BBDB40BAAEE2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7d16bd6904d2f54fa7a8f9d8e326fa9c4cdd2534","datavalue":{"value":"6033901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2883542$77DDCCD5-7CD5-4244-901D-DD96DE77397A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2883542$B84A9DBA-2599-4847-B0A9-4F8BBF246A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd31874a3cb3e5a266e12a7fda1edf899d5972cc","datavalue":{"value":"node degree constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q2883542$EAA64E1F-086C-4D35-9EDD-944213B3CDB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2883542$14A9645A-2D97-465B-B036-76A5E1FAD431","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dfc6b635e8b6b4324d6877f04b011daea3a607d","datavalue":{"value":"proof by reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2883542$657E932A-B6E3-4F1E-85FD-442FB74101CD","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":"Q2883542$401B3E56-8E87-4FD2-90A2-B976C3B744AB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ff87a970a84505d4c3e9dd72c3274362ca7649fc","datavalue":{"value":"https://doi.org/10.1016/j.endm.2010.05.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q2883542$5F84ADD4-57E6-4901-BFEA-0F1F1A8B3EAF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c0a963a0d00325f54f457a1b4127f5946b7df747","datavalue":{"value":"W1545167657","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2883542$5ADD3457-94B6-48BF-9FD7-887DE0486A50","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f61a80df67ff731a2020b0e91f45efc0a213fe3","datavalue":{"value":{"entity-type":"item","numeric-id":2914198,"id":"Q2914198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2883542$5FB7D58A-A5C6-40AE-8290-F75C8CA0CE12","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":"Q2883542$A2450E61-DE5A-466A-B52A-61D898F6F5A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51d868a339dfcce4cf86ed7c20a0ed66abb9949c","datavalue":{"value":{"entity-type":"item","numeric-id":1317004,"id":"Q1317004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2883542$F5160DA4-3488-4661-916A-A284A563DCB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82cbdc4a2ba4de52a71e9bb1596d2f0946f9ea51","datavalue":{"value":{"entity-type":"item","numeric-id":1199130,"id":"Q1199130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2883542$C17881EF-9CE6-4B80-B76B-B7F85E94008E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2883542$936FAC9C-1F82-426B-B745-58BAADF10EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b56ed418b4cf68bf008580e23ec8cb70de24f2d","datavalue":{"value":{"entity-type":"item","numeric-id":3343801,"id":"Q3343801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2883542$C288D25B-A26C-47F3-84B4-3AC427C1EF64","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"96970032903e1940046f5644778444715e7283cd","datavalue":{"value":"10.1016/J.ENDM.2010.05.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2883542$3B44C27A-8579-4CC7-802C-AE8F25F115C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f44b1f6b24a32b923e668e399d14ae455f1d83c","datavalue":{"value":{"entity-type":"item","numeric-id":1853564,"id":"Q1853564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb1b08ea04533c8b5afee69d4cd7e94b26c50be9","datavalue":{"value":{"amount":"+0.810532","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":"Q2883542$D4314B3A-1F87-4EA5-A305-42E07DC42C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e55a226065c6530d39af768c444820bb4097ceb","datavalue":{"value":{"entity-type":"item","numeric-id":5870845,"id":"Q5870845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fae2b0dc2c65aa7e70fcf5bbf6e5951837ea0ddf","datavalue":{"value":{"amount":"+0.8031933","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":"Q2883542$6B8A7A9F-9E85-4880-9153-1220B9C9BF93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dd6a3eb14192a452ebbf1efe9668a7bea0814c9","datavalue":{"value":{"entity-type":"item","numeric-id":3652279,"id":"Q3652279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2eb4957a40b6bc9b1ab058d03afb972cdfc88012","datavalue":{"value":{"amount":"+0.7936605","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":"Q2883542$8E3D3942-AB83-4E1E-811E-BDAEB92D021A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be191024cfb3d35939579efef59dd35594dd4d24","datavalue":{"value":{"entity-type":"item","numeric-id":4608063,"id":"Q4608063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8b2407ccab96c28b9265cb4673123771f8058a3","datavalue":{"value":{"amount":"+0.79241514","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":"Q2883542$5185AFF3-A073-499B-BF70-FF116A7CC922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f745f82cdf798573735f3bb733b943a757fae8b","datavalue":{"value":{"entity-type":"item","numeric-id":6065240,"id":"Q6065240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db4ca6da6eb910667acba49c0a825f658fc4011f","datavalue":{"value":{"amount":"+0.78781855","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":"Q2883542$6417EB80-2CA3-41A5-9F3E-D51137E79C58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfe5dd179830bb6e9aef3970522f0529f51f6f12","datavalue":{"value":{"entity-type":"item","numeric-id":2283027,"id":"Q2283027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da9eda5ff58e1f107c85a523c128347f03aee67e","datavalue":{"value":{"amount":"+0.78660023","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":"Q2883542$8A50E24D-FE01-4314-BFA6-543A93F17ADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3aa25bbf876728f22729cb37941a55171a1a9ad7","datavalue":{"value":{"entity-type":"item","numeric-id":3613758,"id":"Q3613758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2976a24f98589d400c9e8c006e5e7cd1246fbc9","datavalue":{"value":{"amount":"+0.7828279","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":"Q2883542$2F9981EA-EF9C-4F77-8954-8FCC8F92B426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a36b4aae383402c083b7c42e45fef9098100f348","datavalue":{"value":{"entity-type":"item","numeric-id":2492706,"id":"Q2492706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc563c2133023785a3ccfb9a3b102f7005cf8232","datavalue":{"value":{"amount":"+0.78190625","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":"Q2883542$C488E37D-3F13-4048-8A5F-961B1185EBFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8222ceb38be41b3c2e6f8a54668ec346bf6b41e9","datavalue":{"value":{"entity-type":"item","numeric-id":4952696,"id":"Q4952696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc563c2133023785a3ccfb9a3b102f7005cf8232","datavalue":{"value":{"amount":"+0.78190625","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":"Q2883542$8BF8A51B-B2C4-4B5D-95D3-9F00C02487A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9f2580411ac149b2d17b1bfe68582830cec155b","datavalue":{"value":{"entity-type":"item","numeric-id":2674184,"id":"Q2674184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c260c2d2d078ff68bf990a6b4f825ef04499f28d","datavalue":{"value":{"amount":"+0.78173363","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":"Q2883542$0A991699-A700-4409-AB0A-B4745105BB94","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"06a4d7d56de4be1e52d7deae82f208a68fc7bfa3","datavalue":{"value":{"text":"md-MST is NP-hard for \\(d\\geq 3\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2883542$DA97E9D7-1ED1-4420-8B80-6DF2AD07900A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2883542","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2883542"}}}}}