{"entities":{"Q602742":{"pageid":604518,"ns":120,"title":"Item:Q602742","lastrevid":63062292,"modified":"2026-04-11T10:16:21Z","type":"item","id":"Q602742","labels":{"en":{"language":"en","value":"The hardness of approximating the boxicity, cubicity and threshold dimension of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5810801"}},"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":"Q602742$93B5E92F-C282-4684-9F50-C63C53273757","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"381683d3521cdf43db338af6cdb6d958cbca34f7","datavalue":{"value":{"text":"The hardness of approximating the boxicity, cubicity and threshold dimension of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q602742$7BB884A5-D3CE-4DA1-9046-3102572C0631","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f73df43f521893cc6d9d27d01ef699e098135fb8","datavalue":{"value":"1208.05140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602742$882BEB85-D3BA-4F9C-9369-BB960EF17065","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2b2636208b9d972bd743b51d482f0d783c3b850","datavalue":{"value":{"entity-type":"item","numeric-id":475393,"id":"Q475393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$BAB5362A-C984-45B9-86CD-FBAF0770E204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d175eeede2b27cddb50968a88e2761f29308ef10","datavalue":{"value":{"entity-type":"item","numeric-id":602741,"id":"Q602741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$83FAA6A2-CACC-477C-9EF3-4B44C343C8E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"abcd67b883bdb135fa3e2d4d00b0f0c8f6d98bc4","datavalue":{"value":{"entity-type":"item","numeric-id":300471,"id":"Q300471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$0F5EA1B2-9282-421E-AA91-A4F35E29A736","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$51DEAC68-E5B1-4FF2-930C-B4F1748EEB3D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e207171999d8bccd08779f13059dd3836085b46a","datavalue":{"value":{"time":"+2010-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q602742$69386075-D21F-4EF8-8096-DC1C9FA8DE2C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52a68eb72cfbfcf7712ae1f51668490a96882cca","datavalue":{"value":"https://arxiv.org/abs/0903.1010","type":"string"},"datatype":"url"},"type":"statement","id":"Q602742$14BA4D76-B8A6-4C90-BCA1-7626DFD8EAF0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602742$178C51FD-591A-4E71-AF44-8122CE8CC5FD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e48e37690a2a12aa625e070751d384fa84e5bff","datavalue":{"value":"5810801","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602742$27FEB8EB-4915-42BE-B938-30851EC826C7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0019c63940125554689e346877910b261e79216","datavalue":{"value":"boxicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q602742$F9097103-9E1A-451F-BE1F-ECCB5A74707B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba8f9aa88bb3241f9100e65ab8dc861bb79feec1","datavalue":{"value":"cubicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q602742$BFD8D6DC-0C55-4D22-9EE4-36DC1EDDE8A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36c128039aee3cc67b32bab9e0eaba683b60f0f0","datavalue":{"value":"threshold dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q602742$7D1E8F6B-6635-4BA2-A529-8A6412184D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f8e5f0281835e972ada95d61f0a0aee99ca65d0","datavalue":{"value":"partial order dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q602742$00E369C7-B95E-4498-9298-105F5EE25504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8364c4db3fffd0a014142e381813cb4f26f28ac","datavalue":{"value":"split graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q602742$5BE9DFFF-E514-4DAC-A4F5-1F768859CCF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q602742$D2FFF649-63CE-43BA-9C02-54F6D8861F18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e6f2842ba16618da57de12b4c27b4274e41c364","datavalue":{"value":"approximation hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q602742$B038D398-15DA-4E27-ABF8-2A6F8987097C","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":"Q602742$490B1A85-02BE-491C-A70D-37CF0078C96F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"26c134f2d64818a7c273944ae5a957391e851bc4","datavalue":{"value":"W2091388992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602742$E3E335F5-0E5C-4879-90B9-556059EC08B8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"327801a45b790625cc9ae621da22bc5e7d7bf25c","datavalue":{"value":{"entity-type":"item","numeric-id":1025528,"id":"Q1025528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$C7AAE433-1E63-421C-807F-2A44277178B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f3be34444b87e94060eeddaad78e0c69a90fd2","datavalue":{"value":{"entity-type":"item","numeric-id":4165164,"id":"Q4165164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$C7EF27DA-654B-43BD-94EB-0775BDFEC6EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaa1ba9a5d18b08cff3784d8af25cc24ef504e9b","datavalue":{"value":{"entity-type":"item","numeric-id":803177,"id":"Q803177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$7426E2B9-7D39-407B-B852-BECA84E639B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04655507cfa3b8351f7f0657e6f8472d4b8b19a3","datavalue":{"value":{"entity-type":"item","numeric-id":5780132,"id":"Q5780132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$7F2C45EF-D520-4936-96E7-055FBF3B6B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8add4627ebed45e331231c9fcb96d24b9b77ef2d","datavalue":{"value":{"entity-type":"item","numeric-id":4193514,"id":"Q4193514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$F5584FA8-9E92-4F41-9510-DD2268F96FCC","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":"Q602742$E468B915-FD9E-40E4-9836-5C0D2BD921DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d810264bd9487e94aee07c70bd33109da81c98a1","datavalue":{"value":{"entity-type":"item","numeric-id":3503501,"id":"Q3503501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$B9C53031-B366-4674-8824-607D74651A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1152bc7463fcce9eed8b94a2712374316ad80364","datavalue":{"value":{"entity-type":"item","numeric-id":1331895,"id":"Q1331895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$972E4C7C-D24C-497C-8182-13A7C4FBEC00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13ea24d0d08bd225859187316389977dd9b54dcc","datavalue":{"value":{"entity-type":"item","numeric-id":5588433,"id":"Q5588433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$0C77B047-EB0B-41CA-B6FE-0F197B0A2AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fcfd47c3fe9e0f097b76c7c78a15869fd96ffd9","datavalue":{"value":{"entity-type":"item","numeric-id":4004146,"id":"Q4004146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$079F9670-141B-4612-BD15-2FDC1E07243D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"276b2246c2b3fd1d9ece42eec23ea6228fb98f45","datavalue":{"value":{"entity-type":"item","numeric-id":3852226,"id":"Q3852226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$53CAAE6F-289B-43B8-9ECC-840CFF5A4EAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14f316bda1db96a4382c7a9143b182e390b18612","datavalue":{"value":{"entity-type":"item","numeric-id":3663349,"id":"Q3663349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602742$C4C517BA-D185-4AB9-A10F-EC42156CA537","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"74c8ba10239def883f596ea53290275827eb96eb","datavalue":{"value":"10.1016/J.DAM.2010.06.017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602742$9D5D034D-E3ED-4D2E-8202-F07E0FC7636C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf67c63c91a94aefeb6904c40925557a65c04703","datavalue":{"value":{"entity-type":"item","numeric-id":2921679,"id":"Q2921679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e08944a7d57f4996ee6ee8a48390e8ebc7c442cc","datavalue":{"value":{"amount":"+0.9000653","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":"Q602742$B7811D27-9022-4188-935E-9F4E686CE8C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ae14b3be3125bfb86e61f383b080224243fd378","datavalue":{"value":{"entity-type":"item","numeric-id":2741456,"id":"Q2741456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fbd5a9ba8c9d0974ba7d3071f13843fbf7a8c01","datavalue":{"value":{"amount":"+0.88660634","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":"Q602742$6A3BC3C2-BF53-479C-B77F-789126E12ADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"feaa2fb0d3f6e5a26034f29acb1eac1a51ac11d5","datavalue":{"value":{"entity-type":"item","numeric-id":1827857,"id":"Q1827857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fbd5a9ba8c9d0974ba7d3071f13843fbf7a8c01","datavalue":{"value":{"amount":"+0.88660634","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":"Q602742$ECFB52D8-C624-4924-AD2B-D3747D3861FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43fd5cbf529e6f01dfd9098d47112b909f571f62","datavalue":{"value":{"entity-type":"item","numeric-id":4219684,"id":"Q4219684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01d9ee5f1f631290569db4f14c399d50f3a5d985","datavalue":{"value":{"amount":"+0.88490224","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":"Q602742$E04DBB54-9931-478F-B475-105268DC71F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b1e968fd8ec7cf3ec72724abeb2490df17c6fac","datavalue":{"value":{"entity-type":"item","numeric-id":1327235,"id":"Q1327235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"074ed0041a04364bb8480524a3d1d73bfdd4021f","datavalue":{"value":{"amount":"+0.88397586","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":"Q602742$AD09AC1F-5385-49B3-9C52-4A0BACC0BCE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e7e167b849110e50bff57db878424979e1a2edf","datavalue":{"value":{"entity-type":"item","numeric-id":3194690,"id":"Q3194690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"043f7b4968d278a26908ecf51aeaf2c56f61b847","datavalue":{"value":{"amount":"+0.8814628","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":"Q602742$51A9C6B7-8C4A-46E8-B080-7B6C3979D8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3dea0c8894758bc7c6644d8dca19b85ab0c11e6","datavalue":{"value":{"entity-type":"item","numeric-id":1025509,"id":"Q1025509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec1370b2ea66d58ea739dedb75a8e04c14d0c4f3","datavalue":{"value":{"amount":"+0.87957776","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":"Q602742$76AAC5AA-F7A2-4EDC-82DE-11C18A07B0D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e277b740ccc8998402a5770229353a8524e05db","datavalue":{"value":{"entity-type":"item","numeric-id":4724665,"id":"Q4724665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09f4b191d11294622e56eb3f6b9065810ea9b07b","datavalue":{"value":{"amount":"+0.8793547","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":"Q602742$937A61F0-98AA-4525-ACCC-93A8015F06B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e3695d3bec62e671285a4dd2726dcb78770daa8","datavalue":{"value":{"entity-type":"item","numeric-id":4779337,"id":"Q4779337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d99ffff2e846f1c5414631737addb1836b3b59fb","datavalue":{"value":{"amount":"+0.87830067","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":"Q602742$4775A719-519A-463C-BC55-997271A0E3C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdda60f95ce3eca01fd0b7270522db39d9f7f80e","datavalue":{"value":{"entity-type":"item","numeric-id":1025516,"id":"Q1025516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af7f6c9ae49a336241e9b1f95fa2523650c1886a","datavalue":{"value":{"amount":"+0.87428015","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":"Q602742$13FA1467-A9ED-4BE3-8414-E3A6E7D0CB13","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The hardness of approximating the boxicity, cubicity and threshold dimension of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_hardness_of_approximating_the_boxicity,_cubicity_and_threshold_dimension_of_a_graph"}}}}}