{"entities":{"Q2365814":{"pageid":2376557,"ns":120,"title":"Item:Q2365814","lastrevid":72612915,"modified":"2026-04-14T06:04:48Z","type":"item","id":"Q2365814","labels":{"en":{"language":"en","value":"An efficiently solvable graph partition problem to which many problems are reducible"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 222807"}},"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":"Q2365814$143ACC40-84F5-41A4-B1F5-FAA25009D96A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a5c2ddb4e5b7de9f2725350c79d76b33c16054d1","datavalue":{"value":{"text":"An efficiently solvable graph partition problem to which many problems are reducible","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2365814$635A6154-CEEA-47A2-BEAB-D79FDC3A76B1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2324e4d7bba9886bb6fa8fd0fcb829e46107aa9","datavalue":{"value":"0768.68140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365814$FE4A4493-D9E7-4B14-8A4E-BD780164200A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f5fd68296a9f2a303d3163da37e3cbff68763bb3","datavalue":{"value":"10.1016/0020-0190(93)90038-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365814$B5A014E2-DC5A-4317-A874-44C1F7736A50","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":"Q2365814$6F80B341-909C-4979-AFDB-8793D354C909","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2365814$922C3F15-E6DA-46E1-B6D6-99315CBD5A53","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365814$C0B40E70-B21F-41DD-B0DA-90144E0B1EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365814$CFE5CD4F-A1BE-4A09-99DB-A0BD89C04F13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365814$8DD5F2F6-6772-4159-BF46-3A5F8971AD43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365814$8DABE3A2-ABC4-4F52-902C-317CECAE5E15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e47e4f6643776fd50a591a302b22bea051296cdf","datavalue":{"value":"222807","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365814$9080478D-1332-4D78-A7E4-9832888CA60A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"754e317e6f6073c02bd3707bc0e8c155d6a44f3a","datavalue":{"value":"2-colors graph partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365814$4177BE41-C596-4A18-A619-58DA08162407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51c0410216f6db1f0aaf7ec78f4b1eb7c20b723a","datavalue":{"value":"recognition problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365814$611F96D9-B923-4219-BBBD-0CFECE859ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eecb173004633ca38efc326bcd073800d8b745c9","datavalue":{"value":"bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365814$523C0577-E399-486E-B3C6-CFFACBB02E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7fea64311c26df5eb0d4118a99a8ccff13280c2","datavalue":{"value":"NLOGSPACE","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365814$D237516A-60D6-4606-97E7-6EA082021857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365814$0BD178E9-96E8-47E0-97A7-421181428865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7eb269e20bc3d2dab35e25ca61aca273fe6ec003","datavalue":{"value":"2-CNFSAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365814$FDF01143-0EFC-49F8-9FE4-E53450C2AEC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"318bdf490d37de75abdd6ce919d9b1a9c9d31a49","datavalue":{"value":"2-QBF Truth","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365814$2477F707-CEAE-4995-8722-053007CCA376","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"113690841930f39dea3e4af3d50d8c18744a2873","datavalue":{"value":{"entity-type":"item","numeric-id":294732,"id":"Q294732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$65691996-8CA3-4ACA-BA9B-D0AE6BE3E713","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":"Q2365814$0719C69A-73D3-44A7-81C6-9E0DF6A14247","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$5C35114D-0053-4FC7-BB48-133BC8C14049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9bce00e2c1f565d075883522261233bd1b0e65c","datavalue":{"value":{"entity-type":"item","numeric-id":1111377,"id":"Q1111377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$315BEAE8-F765-4B39-932C-D4DCBA4F7186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$7CD9A805-D63E-4CB1-AA6C-B34B4EF202FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14079f9b550ba1f661483da97df5df73cda997ac","datavalue":{"value":{"entity-type":"item","numeric-id":1144050,"id":"Q1144050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$C342220C-C493-4C77-80C4-56986205F62D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1c048b723c40fb7935338c90d19de4fa0f92c9b","datavalue":{"value":{"entity-type":"item","numeric-id":1242177,"id":"Q1242177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$BFAA7B95-24E4-4493-8F3E-8AF2F70CD3E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d43ae11ff137fcfd25f07b9109e47a43bc74b897","datavalue":{"value":{"entity-type":"item","numeric-id":3783310,"id":"Q3783310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$C749F83B-EE6F-4F60-8E36-CF261E1F4954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$2E00957B-7362-43D8-88A5-9CCA1C759804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d396cb7909eb8ef7cf9892a2d4d1be562fcbdc7","datavalue":{"value":{"entity-type":"item","numeric-id":4109298,"id":"Q4109298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$C35AAFBB-73A5-4343-B759-B7AE9B4B85E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebf35f798376b5a791cf663115d6d7824661d5ff","datavalue":{"value":{"entity-type":"item","numeric-id":1199880,"id":"Q1199880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365814$22746925-B374-4628-BB57-059DE007B6EB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d4d0bcb4a50fd6e84408d78fc54db0c23203d25b","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90038-b","type":"string"},"datatype":"url"},"type":"statement","id":"Q2365814$AB48EB8A-BEA9-45D2-A16E-FA827D9622BC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dedcb8e52899732c94dcce370f10546d25907d55","datavalue":{"value":"W2089719371","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365814$ABDD651C-FE9B-4B3F-BFF9-B2F82DC15445","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6996a03be716670f505d0944bdf401eeed72fcb2","datavalue":{"value":{"entity-type":"item","numeric-id":672380,"id":"Q672380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56e7ebe85b45628c4120632d834e7d12a8ad1b3e","datavalue":{"value":{"amount":"+0.7608602643013","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":"Q2365814$33BFFEBD-21A0-4EF8-AE9F-6ABEB198650C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"701d861fad1735148a0ed0e59b352ce8e9aeca4f","datavalue":{"value":{"entity-type":"item","numeric-id":1344531,"id":"Q1344531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"407e6449b77d9d0e273b02f5071ed1f2f11b0ae2","datavalue":{"value":{"amount":"+0.7553107142448425","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":"Q2365814$49C0AB16-5A10-42CA-AC1F-08D1A35547E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8ac034ca9432078cbb72e7cfbaa03a390bdd2d0","datavalue":{"value":{"entity-type":"item","numeric-id":5902303,"id":"Q5902303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7401aa7a9e6e9f72a56602bc9f1b6e7a69ca02bc","datavalue":{"value":{"amount":"+0.753071665763855","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":"Q2365814$E9EA4919-52BE-4695-A9D5-7DBB722C8834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7630905db3edec58c8b83d2138bb5de07ac6948","datavalue":{"value":{"entity-type":"item","numeric-id":2479574,"id":"Q2479574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ebf52d9831eeaa5b68b7119b89634d7113b6aaf","datavalue":{"value":{"amount":"+0.747999370098114","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":"Q2365814$6CCA27E2-0015-4F59-BEB0-DBF588744D46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd14f14fb59fbc338421a338cd62ac6b05c7444d","datavalue":{"value":{"entity-type":"item","numeric-id":3544241,"id":"Q3544241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"380d209517300e58982270c4fdc2a1fe2dfbdca7","datavalue":{"value":{"amount":"+0.7466290593147278","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":"Q2365814$6369BC0A-BCFE-43F5-88ED-B4FFD2513EBC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficiently solvable graph partition problem to which many problems are reducible","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_efficiently_solvable_graph_partition_problem_to_which_many_problems_are_reducible"}}}}}