{"entities":{"Q2407090":{"pageid":2417833,"ns":120,"title":"Item:Q2407090","lastrevid":74122878,"modified":"2026-04-14T18:30:03Z","type":"item","id":"Q2407090","labels":{"en":{"language":"en","value":"Minimum bisection is NP-hard on unit disk graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6782876"}},"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":"Q2407090$184BBCCE-1EE7-4B22-A772-DF49C460FF59","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"31963130ddb04c60ae332865f21aced8e94d2fad","datavalue":{"value":{"text":"Minimum bisection is NP-hard on unit disk graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2407090$A0E0541B-5B2A-418A-91FE-54568740CB1A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"25d3da85a292e5d019012b099fcd6426667034a7","datavalue":{"value":"1376.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2407090$D60871DD-7402-4D9B-8568-7980241D65A3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"01c7c91a252c5355934715212b81e739aaf74478","datavalue":{"value":{"entity-type":"item","numeric-id":261371,"id":"Q261371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$9A802A72-9487-45BB-A69B-222F17FCAED7","rank":"normal"},{"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":"Q2407090$A0C6FEA5-CB45-467E-BFAC-9216566C3FF5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$20E7AAF2-2CD8-494D-BD7E-7D03B06AB602","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f72265dfaac0bc8e24a1f91fd4a1bc20423d8c4c","datavalue":{"value":{"time":"+2017-09-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2407090$1646C2E5-B7F9-447E-AA0A-6C991B620AA4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a1fe0549e81a676602eb0f1a882b9939dee3b29b","datavalue":{"value":"http://dro.dur.ac.uk/19737/1/19737.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q2407090$23B1FE43-1DC7-4B1B-8395-029231FFFA81","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2407090$5A8E7A5B-4B91-43D1-939A-229B219A38EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2407090$93375976-997C-4215-A5DB-A415EB422664","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2407090$A3FFC620-FCCA-4892-A5F3-F743581D227F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71df56b7dd531aae0a5d8455fa7544c99a1383ed","datavalue":{"value":"6782876","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2407090$1BCE6088-31CC-48CE-8FD6-63E1C1FA26A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c7dd789e496401f6fe4e6547323886ec1856ddf","datavalue":{"value":"minimum bisection problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2407090$049DB952-8EBB-47C6-82CA-89B6E3478224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd00c48d13560af13a3d1074cbfb041f87deec30","datavalue":{"value":"unit disk graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2407090$7FEC0A32-6714-430B-BA22-B817A172B637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2407090$1F68D19E-B536-4F20-AF4C-9F1C3F4BF4FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2407090$78008884-0234-4533-9A2B-838EDEBC7E35","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":"Q2407090$429CCB96-AE55-4D38-8FEB-D8744C9EBD00","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"424736059e4441cbebcaee75898b8ce0a77e2253","datavalue":{"value":"W2609264909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2407090$0E537FA2-1023-4059-B953-4AD2387DF952","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d627e3e82fa62aab706ada7d24a4c11b1752bef","datavalue":{"value":{"entity-type":"item","numeric-id":2889270,"id":"Q2889270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$F1FFC92A-4FA7-47A5-958E-03AB4B52AC4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a44f31abbdd4dc84e5f661896a7812e44411ddf","datavalue":{"value":{"entity-type":"item","numeric-id":4100093,"id":"Q4100093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$E3F98164-9149-4AF9-B0F4-F1A9423B06CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34a9763aa532dcac8b0fe12a3cbb5ae34d995fc5","datavalue":{"value":{"entity-type":"item","numeric-id":5233715,"id":"Q5233715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$4A531284-C071-40F2-843D-4E6D688366E6","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":"Q2407090$F4D43A0E-0186-40CA-8930-050CD2ED66DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a30615c5e90cb12d37f7f5724296be9ec73ec8ca","datavalue":{"value":{"entity-type":"item","numeric-id":5259566,"id":"Q5259566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$4D1AF33B-6310-496C-A79D-17489FF81FEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26124a7921177e17ad902488e0bc3298a3f3c43a","datavalue":{"value":{"entity-type":"item","numeric-id":3549709,"id":"Q3549709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$21D0CCD8-5134-4869-9A90-0E7E6ACB398F","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":"Q2407090$F5979164-6ABA-4272-8D43-157AB50930B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adf5f350d371d79094fe6803144ac782153f67f2","datavalue":{"value":{"entity-type":"item","numeric-id":4866677,"id":"Q4866677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$52679BBF-8BC8-4A69-9F4C-F85BC40C2CF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32e5661da29c0c8d8e48a8c6276ebe8dfc898e5c","datavalue":{"value":{"entity-type":"item","numeric-id":3092224,"id":"Q3092224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$2F0DE703-3214-4F4F-99D1-4DC69DF2AAEC","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":"Q2407090$1671F6C4-0F7F-4BD5-BBD2-711C3894430F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7299c3309f1595404d86c1c96d3a1c04dcd2e81","datavalue":{"value":{"entity-type":"item","numeric-id":4708558,"id":"Q4708558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$D5C201AA-CF9F-47DA-B612-107E429A3913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5d824fd7864db7373cffb24e8e389ae2c0b8463","datavalue":{"value":{"entity-type":"item","numeric-id":5417718,"id":"Q5417718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$E9352E44-814B-4002-9780-4A2DE413A315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bb528b41dd0031e8fa7428dc83ad752249dea8e","datavalue":{"value":{"entity-type":"item","numeric-id":1773296,"id":"Q1773296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2407090$AB5C3C65-2097-4CBF-BD7E-FCB242247692","rank":"normal"},{"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":"Q2407090$BEFA4390-BC26-49B4-B6B8-079627F30664","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":"Q2407090$7B37450B-960B-4D35-B851-56F44DE0AD2F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2e2e2dec008589a746ae77ab1fce0957c1d56724","datavalue":{"value":"10.1016/J.IC.2017.04.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2407090$41ABB539-526F-431A-967E-D3F98624F97E","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":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$9BAB3651-36A7-4566-BEDB-094E70CE1824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad3f519789fa9bc3fc1aefac5608d68e480f550f","datavalue":{"value":{"entity-type":"item","numeric-id":884483,"id":"Q884483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7b6cda5fa966596b55f2a5f0a8a9ff53011fd59","datavalue":{"value":{"amount":"+0.9290505","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$D899D5EE-15FF-47AD-9762-2B37A4CFCE54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2996ad39b402b3544371111e726d7d492446c69","datavalue":{"value":{"entity-type":"item","numeric-id":659693,"id":"Q659693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b60049c093592fd5561733efa03e443cfca71fba","datavalue":{"value":{"amount":"+0.8828004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$739E69CC-BB85-460D-9B95-2668BFC18962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2e7b86af9b509f5ea108cf5bc2c9b9bc1fa5ca8","datavalue":{"value":{"entity-type":"item","numeric-id":322301,"id":"Q322301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d11b48d9b447ea6b86314120500e092d8b769b8","datavalue":{"value":{"amount":"+0.8687067","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$8B4BEA62-6215-485A-8717-3B3897E5EC67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74f901ea5f64ffe127f56978b06be8dead144bc3","datavalue":{"value":{"entity-type":"item","numeric-id":747771,"id":"Q747771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed4344fc93d1fd249f3a6c13221d1a999fe98cb2","datavalue":{"value":{"amount":"+0.8650328","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$F44B2D1E-9068-4AA1-AFAF-30AEE30B6207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c81a2ed3054186d5949ef6530267cafd4f9b572","datavalue":{"value":{"entity-type":"item","numeric-id":4708558,"id":"Q4708558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b46d8ea0872b0d54c2d94b84ed7c974860394541","datavalue":{"value":{"amount":"+0.8643001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$7EE8C59A-67FE-4625-B3A5-D4B08CA71202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90dfd5dab00a1c051c02c7d912bfff161795875e","datavalue":{"value":{"entity-type":"item","numeric-id":3459050,"id":"Q3459050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af05983eab49df6a4b8acae686666db99bfccf4e","datavalue":{"value":{"amount":"+0.8638852","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$6BD5231E-E03C-437C-96E0-4754EB4CBF76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bf7b7bd68598b58724800e09b49e9809129f90f","datavalue":{"value":{"entity-type":"item","numeric-id":4033892,"id":"Q4033892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58bb0f6183d5f143aadd91429f7076f2c0bd0080","datavalue":{"value":{"amount":"+0.86142987","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$4A6AA87B-00C0-45B4-8EFD-3B6EB21B9F82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24f571f8b8bc27c3ac475299ef9c91cfb60f3607","datavalue":{"value":{"entity-type":"item","numeric-id":4634024,"id":"Q4634024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63cf85f3c21ea8109dff53c25d69486fde5cc25c","datavalue":{"value":{"amount":"+0.85981387","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$569BC0E1-F950-4A3F-9E88-050619C54BC2","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":"35cf143f7348fe13bdd6dc1d0956448f8258482b","datavalue":{"value":{"amount":"+0.85939586","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2407090$7CCA27AD-A4A2-4168-BC9C-44D8BCB13EAB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum bisection is NP-hard on unit disk graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_bisection_is_NP-hard_on_unit_disk_graphs"}}}}}