{"entities":{"Q884483":{"pageid":886331,"ns":120,"title":"Item:Q884483","lastrevid":65087202,"modified":"2026-04-12T00:13:30Z","type":"item","id":"Q884483","labels":{"en":{"language":"en","value":"MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5161900"}},"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":"Q884483$B8911AE5-CB85-485E-9132-9C6A628E9457","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5941874b51bd3e1d02a0b04c6ced98c713846c72","datavalue":{"value":{"text":"MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q884483$8A8D8ED3-472E-40D3-ACF2-0105D6B5E81C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"81396b6098a77653c7be611318487334849fb124","datavalue":{"value":"1118.68073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q884483$C816F2DD-3346-4CF1-8893-99A2B2B50552","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":"Q884483$D5437078-5BBB-4FAB-B5F7-77DF16E85C50","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e01af03b171e8da4ad9abd5d8746451ee7976176","datavalue":{"value":{"time":"+2007-06-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q884483$8F7DF494-3AB9-474D-9F26-F436D36F8656","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q884483$605C2E9C-BFA9-43A9-95C2-C23FBC973AA2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"042322a52bb5c55d21f07d926792b8d14d01c543","datavalue":{"value":"5161900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q884483$DF6D12BB-9A46-450D-BF56-34DEDE49C54B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q884483$4D216527-54F8-471F-AED2-5663A0C69254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a22e7d1abd8c994aafbaa0e81a87650ac884dce","datavalue":{"value":"Max-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q884483$5DB6037B-8174-4A81-92D5-E18C9DA407B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bed6d6ef845b230acf75b133065d90f843ea28af","datavalue":{"value":"Max-bisection","type":"string"},"datatype":"string"},"type":"statement","id":"Q884483$A6C06D77-93CC-4693-9B93-2A8A642A7730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q884483$7108493C-D25A-4DC7-B1EF-75B76F40FAA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd00c48d13560af13a3d1074cbfb041f87deec30","datavalue":{"value":"unit disk graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q884483$ABB4DCA8-3D50-48E9-895A-945D0A189CB7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2dca00cf5e3506d17c2986004891f80ecd82aa0","datavalue":{"value":{"entity-type":"item","numeric-id":314817,"id":"Q314817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$0A55371E-93A5-474D-A5EA-00BB829AD187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1aee8b2e156a4dc08f28586a944ab8da5a4e706d","datavalue":{"value":{"entity-type":"item","numeric-id":191506,"id":"Q191506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$1422A2D4-6B71-416B-BCF6-A1EC54EB3F98","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":"Q884483$81E543BA-4410-4824-9720-6668D45E287B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"512c6bfd0092f0b91c11f6d3c17016e13d7ac318","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2007.02.013","type":"string"},"datatype":"url"},"type":"statement","id":"Q884483$AF091F09-01A7-47D0-A920-E3E235F94BBA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9cfd46faa508a3c686c1a5a06dd36ac131f22377","datavalue":{"value":"W2064530627","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q884483$0768467E-D215-4EB8-BC2C-487E53ED6F5E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4a381dce4100bafc346fa18a9f4f26641825a6e","datavalue":{"value":{"entity-type":"item","numeric-id":1384186,"id":"Q1384186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$5983CFA4-EA6E-4A6B-A0B5-FA3F04FCC9F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c95c8cc477f321463edbd539a33c0c0930191272","datavalue":{"value":{"entity-type":"item","numeric-id":4500843,"id":"Q4500843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$9F551037-7311-466F-BE43-14EC2129005C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f380170dd9de5e69fb40eb46470ac085e19dc87a","datavalue":{"value":{"entity-type":"item","numeric-id":1174134,"id":"Q1174134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$801BD13F-EAAE-4380-AC4A-39022C8993C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f5e4c412e1b522bf1123cf9a7bc8e6688e7aa41","datavalue":{"value":{"entity-type":"item","numeric-id":2731603,"id":"Q2731603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$081E2471-DDF5-4BB9-96F7-0D3E0070DB8D","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":"Q884483$4035074D-C533-45DD-84A2-8D18E97789D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$4D2A0824-49F2-451F-B060-97D2C4050188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849849a8734e624cdd488bd27603bced49d0bfd9","datavalue":{"value":{"entity-type":"item","numeric-id":4083698,"id":"Q4083698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$5F4F3053-C5C1-46B2-A851-6046D67506E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6987cd6c0def26f03a95695d16c29cab043a89e1","datavalue":{"value":{"entity-type":"item","numeric-id":4386448,"id":"Q4386448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$5A2AB8EC-5CFB-4F0A-B838-A5A6679756A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85c273f974b452d3840b58e29b5a78db393786ad","datavalue":{"value":{"entity-type":"item","numeric-id":5700571,"id":"Q5700571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$1BFF5475-E3C8-4C23-A113-2889A53A9C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$966CD237-12E8-4D66-B4FF-55BCB581F5EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3f8720cd5cf76532f632147aaa808ac8611f08f","datavalue":{"value":{"entity-type":"item","numeric-id":5757904,"id":"Q5757904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$89BD1A51-8795-4DEF-AD12-A4FD581D8F6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ff469158b0917cd489eec9d6ddfd641a6e6e677","datavalue":{"value":{"entity-type":"item","numeric-id":5659589,"id":"Q5659589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$86501474-08DF-4D2B-A4EE-85578FB75E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69f254905ff1ada4c9ba698b1b0da28d301a3fb7","datavalue":{"value":{"entity-type":"item","numeric-id":1396949,"id":"Q1396949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$2F3AC7AA-49C0-47FD-812A-BC61FB0B126E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53931acda4d1de6fffc8c785b472a64b77dbbda9","datavalue":{"value":{"entity-type":"item","numeric-id":5402565,"id":"Q5402565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q884483$67399060-4A52-4F2D-87D1-2DBB72C77155","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4e662ba104eac66d9ba9fe27bc9fd0807a45527e","datavalue":{"value":"10.1016/J.TCS.2007.02.013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q884483$A506E2A3-F939-4A84-A113-A022E3BB19F5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b47da97deb76a861905c945437f2863d81328f4c","datavalue":{"value":{"entity-type":"item","numeric-id":2922613,"id":"Q2922613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b4e8541d26c8235e184d614bb9a850370f6c56a","datavalue":{"value":{"amount":"+0.8798547983169556","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":"Q884483$EB9D5EF9-068D-4BC4-8685-0C462B919707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a5c3f6435b1538290444fb01296c1db128d786e","datavalue":{"value":{"entity-type":"item","numeric-id":1384186,"id":"Q1384186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c0a87e71eb5ba36a44682269b68ee13e2d301a8","datavalue":{"value":{"amount":"+0.8095798492431641","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":"Q884483$B69006B8-9FC6-47A6-8F2E-5053ACC4366F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbbf27bc3e3fbbf893c909002a434f1cf0df6575","datavalue":{"value":{"entity-type":"item","numeric-id":471386,"id":"Q471386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b9c6980c248deedd9a45b64d60ddd4d0343cac0","datavalue":{"value":{"amount":"+0.801740288734436","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":"Q884483$512AAD95-9B8D-4725-AD0A-463AC474FEDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17d9db1a0450f1f8429cc29c9ca9d0eed3b26a16","datavalue":{"value":{"entity-type":"item","numeric-id":1174134,"id":"Q1174134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"563bf9b3b32795ccb14b76e949ae8d076f13fb22","datavalue":{"value":{"amount":"+0.7981266379356384","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":"Q884483$37740C85-DC24-402E-A7F1-B8B627F6E7CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4856c52bcbac151d813b90b2fffc67a97bc1791a","datavalue":{"value":{"entity-type":"item","numeric-id":510977,"id":"Q510977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"563bf9b3b32795ccb14b76e949ae8d076f13fb22","datavalue":{"value":{"amount":"+0.7981266379356384","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":"Q884483$28BAA3BE-9A2A-464F-9BE0-7EC254068CEC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/MAX-CUT_and_MAX-BISECTION_are_NP-hard_on_unit_disk_graphs"}}}}}