{"entities":{"Q5402565":{"pageid":7432139,"ns":120,"title":"Item:Q5402565","lastrevid":41677546,"modified":"2025-05-07T02:56:12Z","type":"item","id":"Q5402565","labels":{"en":{"language":"en","value":"Node-and edge-deletion NP-complete problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6270125"}},"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":"Q5402565$D92903A9-35FA-4B95-B17E-1FEC3BD5DC9E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eec6ebcc3ba74c8ecbc1e9d192399aef826a9ebc","datavalue":{"value":{"text":"Node-and edge-deletion NP-complete problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5402565$F61E02D1-8386-48F4-9888-42C975D49F34","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"76f1e9c55f28018919ac0116f7d2599cc5a0b576","datavalue":{"value":"1282.68131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$EA7C375D-D226-4744-8B5A-7A709F31437A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e6b9cbc1ceeace07ba2c73c11267199a37ac80da","datavalue":{"value":"10.1145/800133.804355","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$A1DA2A0D-4DDE-4A82-8AFE-BDAD3A372B87","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"64789e48fd3ab0a44b5ae0aa6d85c1c024312026","datavalue":{"value":{"entity-type":"item","numeric-id":458479,"id":"Q458479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5402565$0B0D38C0-A7C6-4D85-B7F8-0F5EBC089C20","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2829c1a1386220ab006ee0a1468db55a2e8980dd","datavalue":{"value":{"entity-type":"item","numeric-id":5402534,"id":"Q5402534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5402565$1B94150A-9A7D-469E-AC02-F46A6CCF53C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b43a2c2b6eb630f564616ba070a6751b081d8977","datavalue":{"value":{"time":"+2014-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5402565$EF5EC796-9FF1-4394-9329-B3A8787CA6FA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$D42C78B0-40A1-4CDB-AD5D-4916671924C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$3151EAF6-CE27-46DE-BEF0-903BE39CA3CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$859F60F0-0492-4CBD-B4DE-230B4BE35BAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$24BDF4DA-ED11-41BD-AD9D-A0A80C5D0DCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$3C5FF08D-68C4-488C-9EEB-4C35A88C1686","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e0d0416f664dbe6f550d5ccda2dd41d4e9a2b499","datavalue":{"value":"6270125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$46553D3B-43BE-4FDB-85A7-38464D4020AD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$F8E566D3-D225-48FB-9F6B-838B2F5FC09C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$8B7A0EA1-CA52-4967-88FD-10211A7BA933","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e2847eefec0179e00a7eda84e333666b3de1a15","datavalue":{"value":"edge-deletion","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$0670BB0F-4511-464E-8447-9719191B505B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddc14051a93e8c78a1da682d6f4184d91e9c6088","datavalue":{"value":"graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$BBD3499A-B05B-4A61-A398-A2AF9592F872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c1e60e4f93a5eb203519f7e80f10a7da2a710e9","datavalue":{"value":"graph-property","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$98A833DC-258F-49EA-A282-D6250F587A2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1dda56e42d3ec16ced39df375dba919c9c4f46e","datavalue":{"value":"hereditary","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$A3981959-2ADB-421F-9220-C977FCFE5BE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7950e855b95d9f16625744632a0923df4db6e58e","datavalue":{"value":"maximum subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$EAC3D36B-2BD6-4957-BC85-AD94AE6E34BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$74BF1531-064D-41E1-B60A-C78C49C5480E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4212d7406535f21183dc10e7cab2964d06740910","datavalue":{"value":"node-deletion","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$E93DC332-C3C4-4C1D-BC4C-8027D53A4158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"154ea0589dca3b50bef0f626c64f0e117c0eb521","datavalue":{"value":"polynomial hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q5402565$E6B46B8D-EFBE-4FE2-9DB1-B3AE2105A455","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b8126a365cfb8fac79f36f7df4612bfaa436969e","datavalue":{"value":"Q56209809","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$42C30F46-229C-4ED6-AA98-A8F739AEC9FE","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":"Q5402565$59ECFBD5-E2E9-4C75-B52D-1AC9F2A92883","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8d372fc8d0f8352a09bee64108510f6555b7ae09","datavalue":{"value":"https://doi.org/10.1145/800133.804355","type":"string"},"datatype":"url"},"type":"statement","id":"Q5402565$D7FD757A-AAFB-45A6-86B2-48206AB92543","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"74d29160f6c250194ade2b6d1773f9e99bc51861","datavalue":{"value":"W2045027193","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$3AD4A216-CE53-48A5-BAE0-E48E934E9624","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"79163d4ab2f43387a6b5e0b271c20be772a4b257","datavalue":{"value":"conf/stoc/Yannakakis78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5402565$7F77C7AD-67C8-43E5-8C56-397D09A24E50","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f862a3c776fa2be3f6cc0e933561a08d056ce5d9","datavalue":{"value":{"entity-type":"item","numeric-id":3801094,"id":"Q3801094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93501aa7e2330b19be70ce4619838010b4ce4007","datavalue":{"value":{"amount":"+0.9307225","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":"Q5402565$AF9C0872-A157-4DE5-A81C-D7EFD2B0AB39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"105fdddf910230fff1483c3872dd92a40b51dbef","datavalue":{"value":{"entity-type":"item","numeric-id":5387826,"id":"Q5387826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cd66ff33fd07992ab336c55e2aa69271f2bfb01","datavalue":{"value":{"amount":"+0.9095981","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":"Q5402565$0D4C18DD-9231-4B8F-A4F0-9D571E7ECD90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bc6fb751ab0e9293b636bdb8e64b50f50ff82a2","datavalue":{"value":{"entity-type":"item","numeric-id":2333799,"id":"Q2333799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be227c477235946a93f94282d3344c5354e7a960","datavalue":{"value":{"amount":"+0.8917115","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":"Q5402565$B5B152E0-0FA3-411A-ACBF-93E859AEB55D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a26663bdc453fc9480abca5311819761cdd6f6aa","datavalue":{"value":{"entity-type":"item","numeric-id":6057334,"id":"Q6057334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5848757688fea7055ab4d6b14936ee2e0aaa2478","datavalue":{"value":{"amount":"+0.89115787","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":"Q5402565$539D6B5B-2661-439E-95C0-BF5B83FD9913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f8d7ee34b974bc8121361c2a9a1ea811daddfd2","datavalue":{"value":{"entity-type":"item","numeric-id":1897369,"id":"Q1897369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"030a80a8ab117cb4ee0ddd30856194e24511eda1","datavalue":{"value":{"amount":"+0.8894609","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":"Q5402565$70B58271-E5AE-40F0-8C66-2188D8CF1A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93f0dfb2364bd3b064e1036b1f04cad92194da3d","datavalue":{"value":{"entity-type":"item","numeric-id":1029021,"id":"Q1029021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f546b402db30d72620d803baf34c096e174bfc3","datavalue":{"value":{"amount":"+0.8893243","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":"Q5402565$DC8DC527-85DB-4959-9295-493A5ACCFEED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8eb5f46b8914aa35776db4171be805092998b8f0","datavalue":{"value":{"entity-type":"item","numeric-id":1270821,"id":"Q1270821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2b38b4ffd983525c61a1767a06eab3d0de90496","datavalue":{"value":{"amount":"+0.88876086","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":"Q5402565$9B651CD4-9A8F-4329-A691-CA1B89C83994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05f8b6b338d53c1f4a282524ac658b6cf37bdbe0","datavalue":{"value":{"entity-type":"item","numeric-id":2257301,"id":"Q2257301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f6c8c91d369e69323789414d71ab155c11ae965","datavalue":{"value":{"amount":"+0.88729185","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":"Q5402565$9C25F6DB-B70F-4EAE-B41F-347A08C85F82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"550d5a70ec9f82b456f55e26bc7c12ca6eb4935a","datavalue":{"value":{"entity-type":"item","numeric-id":1786595,"id":"Q1786595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4c4df333846b04d597b70daad3f1251f4b3ed15","datavalue":{"value":{"amount":"+0.88349277","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":"Q5402565$FEAFBDB0-5BC6-42D3-95F3-3755D15A3CB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b7b1fdcf899234919273a745b2730491bd1148f","datavalue":{"value":{"entity-type":"item","numeric-id":5136314,"id":"Q5136314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4c4df333846b04d597b70daad3f1251f4b3ed15","datavalue":{"value":{"amount":"+0.88349277","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":"Q5402565$0DBA6A8C-DAFB-47CB-97C9-56C9D939BA3A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5402565","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5402565"}}}}}