{"entities":{"Q1198051":{"pageid":1208800,"ns":120,"title":"Item:Q1198051","lastrevid":66847227,"modified":"2026-04-12T13:15:25Z","type":"item","id":"Q1198051","labels":{"en":{"language":"en","value":"Finding good approximate vertex and edge partitions is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92110"}},"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":"Q1198051$6E491608-30DC-400F-960C-33229C71D3A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e98a8529cf204fc0465db1e5279fb14e0c692095","datavalue":{"value":{"text":"Finding good approximate vertex and edge partitions is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198051$8EB51739-6581-499F-BF14-CE69AF670E3A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a8b8decee47a309652bd23c8c9e263bb155eea8","datavalue":{"value":"0764.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198051$FE4B0403-6BD0-4B1C-9B62-46EF6CD4CB9A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aea4902425d96a9f5bce68d61a0dc491dcb7ac1e","datavalue":{"value":"10.1016/0020-0190(92)90140-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198051$F54C7418-2C64-4C46-983F-B100C91C3F70","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60c35072af6feb5ceaba6f28a7791fbfacce4a92","datavalue":{"value":{"entity-type":"item","numeric-id":1198049,"id":"Q1198049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198051$B0533496-E8DC-4CAE-B13B-E0A338D97291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea70d309349f9ba471304ff216cf56dd2c5503ad","datavalue":{"value":{"entity-type":"item","numeric-id":1198050,"id":"Q1198050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198051$B1E95E1C-138A-4034-8C25-ADFB72352188","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198051$D80D7975-F1F0-4100-96DD-66F46ABD1526","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198051$6C2CF113-654D-46C6-9B9E-450E9686EA3F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198051$EB3DD345-ACD9-4B4B-A0D2-947DAD9A89BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198051$99464EF0-643F-4E2B-9D59-D2B81C0B0E26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198051$DDE35359-C1FE-4F12-BEE6-8C8B3DB716EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198051$05B78F68-E72B-41BB-AC1C-3382F16BBA18","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5f5fbbe8a59052e4fad1031a20313883ca09c2f5","datavalue":{"value":"92110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198051$9A43E07D-0432-4E0A-ACCD-A95CA29C32CD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e242af08a265f147fecdde71acc893f1df2b816","datavalue":{"value":"graph partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198051$FA3429D4-AE21-4DDD-819C-D068E0C9E7C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198051$05F74D26-A356-44B3-94F7-0ADF4454BACD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198051$31DF5E68-5CC5-4C72-AEFC-3A6B151AF0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e2a6bd9ce52f8723050176cfb86ffa478e7a47f","datavalue":{"value":"separators","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198051$4700C418-FD22-40E4-A71F-6F93695720AF","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":"Q1198051$47C84378-2123-4796-BAD7-1BDA936E51CA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe7750ade2656a46edba3443fde7d8b689ecfb58","datavalue":{"value":{"entity-type":"item","numeric-id":3990649,"id":"Q3990649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198051$930158EE-3B0F-48FF-A4F7-243A349F9094","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198051$FDAC3C2E-47B9-4B7D-9D89-1ADF3CD3AF84","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":"Q1198051$2EBB1657-42D5-4B7E-B79F-4C2433162897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198051$9622C41B-23F0-443D-910F-4080232984D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3a65789551f0f46ea65e1245aaba062fc584dc5","datavalue":{"value":{"entity-type":"item","numeric-id":3474888,"id":"Q3474888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198051$0B4359D8-73FA-429F-9641-35311C8EF61B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e9925e4c3b9e6e42694883bde8922edb89e66c3","datavalue":{"value":{"entity-type":"item","numeric-id":1179551,"id":"Q1179551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c68a629403af53a3fa05f957b7575e49c2207f15","datavalue":{"value":{"amount":"+0.8065641522407532","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":"Q1198051$6CFE04A4-674F-42E3-B701-63B56790B6FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b78780cd59dc681fac18418166f17f97384f694d","datavalue":{"value":{"entity-type":"item","numeric-id":5301395,"id":"Q5301395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa2b15c99f09ef986bcabdbd6c5c85512c9616a3","datavalue":{"value":{"amount":"+0.8049651384353638","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":"Q1198051$90F2FA1A-7DD0-4165-89D7-C48DDF95E605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3027cfc989bebc315ce692eb469b9d73af114486","datavalue":{"value":{"entity-type":"item","numeric-id":3474888,"id":"Q3474888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f6f3f91e1f0040fb883d13888ac530995b85819","datavalue":{"value":{"amount":"+0.7897396087646484","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":"Q1198051$D3131407-AD71-45AE-9050-FDCFB64A8DB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"425048148aaadca02dec9185cd8d2729aaba2487","datavalue":{"value":{"entity-type":"item","numeric-id":2931401,"id":"Q2931401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e9e6557e06fc75a82ef720ec360bb5bf49c3e65","datavalue":{"value":{"amount":"+0.785788357257843","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":"Q1198051$A2D48B20-5E5A-4D66-8B1D-E2EA6790CA0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3b4f571f4b589c18fa8f904e281e4cb599eabd8","datavalue":{"value":{"entity-type":"item","numeric-id":3192022,"id":"Q3192022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9782f1dae635ddc92b36440b9e03c971a8d5940","datavalue":{"value":{"amount":"+0.7596032023429871","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":"Q1198051$BEBB5691-E25E-4622-BAC5-0F21AA5FAC08","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding good approximate vertex and edge partitions is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_good_approximate_vertex_and_edge_partitions_is_NP-hard"}}}}}