{"entities":{"Q1744983":{"pageid":1755725,"ns":120,"title":"Item:Q1744983","lastrevid":53068901,"modified":"2026-01-24T04:04:08Z","type":"item","id":"Q1744983","labels":{"en":{"language":"en","value":"Computational complexity of the vertex cover problem in the class of planar triangulations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6862370"}},"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":"Q1744983$951512FB-EFDE-403B-B551-262EE6D28E6D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a648111ec097d62959b6e136b78dce0f3a20dfd9","datavalue":{"value":{"text":"Computational complexity of the vertex cover problem in the class of planar triangulations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1744983$758462E0-2B48-4C39-9ED3-E16F1F7C4200","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"37ff927ee5569e58412cb0a7ecba934d7d1e8b15","datavalue":{"value":"1388.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1744983$8B350426-D469-4A68-859D-57083CEC4E64","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fbc2fe9d32271f81af8a9789b6d3f8c6ae0542eb","datavalue":{"value":"10.1134/S0081543817090139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1744983$1B9DC7A3-FB52-4611-B82B-66FD34BB6F76","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"65ce7905050b3321b6de8e2b21b0b7fb3a04b453","datavalue":{"value":{"entity-type":"item","numeric-id":492283,"id":"Q492283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$FAC3D489-A3A3-4BF4-843A-490512CDC185","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52ab463cca8ead400441fcc2b4fac1f6fbb55915","datavalue":{"value":{"entity-type":"item","numeric-id":251486,"id":"Q251486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$B18C8D2F-55B0-4127-8CC6-A0BAE0910B82","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2e3e9e889e4401b37d32bcf9af4f161f7364a67c","datavalue":{"value":{"time":"+2018-04-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1744983$8006A984-2D78-4BAF-BC1F-3BAA7AE1426D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"813d3235c4d3ea319742f2fbebc1e6079f4b728c","datavalue":{"value":"It is shown that the vertex cover problem is strongly NP-hard for simple 4-connected planar triangulations on \\(n\\) vertices with a triangular outer face and vertex degrees at most \\(\\log n +9\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1744983$8A52F740-C823-4CA2-95AF-D3E05E77AC6E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"706e08216f8d7e32a9bfdcc84aeeba4ad0f22d8d","datavalue":{"value":{"entity-type":"item","numeric-id":169304,"id":"Q169304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$07D2BA52-1C77-4701-BC83-AE7F7CBD3FDA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1744983$277AAE74-A2A4-463E-BCF4-94462F0489CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1744983$859F5AAC-990E-4EDC-B090-2EE4599120D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1744983$67F371B9-FD38-4E9F-9757-BEB771EDC140","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4ba1acc7fe762e5dce65a18cd2e0a1d8607684f1","datavalue":{"value":"6862370","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1744983$2FDC5F36-393F-48E4-8708-4E4B1DF66AFF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1744983$27C2C8FA-E637-489D-8291-3734EB92FB0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5edfd6368999620c7e10cbba2e058c2b660abfd0","datavalue":{"value":"Delaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1744983$63771D51-0B03-4A20-A2E7-C15F33171FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f64f976dd1556a1bbef5eee4ef7449b907cc73fa","datavalue":{"value":"Delaunay TD-triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1744983$0C84913D-6619-48E4-B0F8-9949912BF891","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":"Q1744983$400E8E06-2BC1-4BD9-BAE7-EBA3A295EAEB","rank":"normal"}],"P223":[{"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":"Q1744983$D37DF2DF-3E7D-4B47-A945-7F15609672B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d0e750805d5b78bc4e63a95a9bf276bc2c16c4e","datavalue":{"value":{"entity-type":"item","numeric-id":904106,"id":"Q904106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$882F7159-7E84-4B0D-AAC6-098C10FE6D71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57515aea1ad564d767f2a1d2b4fdb04b8bf50ff4","datavalue":{"value":{"entity-type":"item","numeric-id":1274912,"id":"Q1274912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$A3A0CD6E-DC0A-4147-AAD1-424A00DDD7F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3614b07925bf11635f52dee1649c0e1683b8b46a","datavalue":{"value":{"entity-type":"item","numeric-id":2346341,"id":"Q2346341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$DC0825D5-24CE-4B03-8C6E-53DA5FC51305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"039182aed8830a54f2e006f37e4eb6d607104ef9","datavalue":{"value":{"entity-type":"item","numeric-id":3057631,"id":"Q3057631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$61BC7BCC-CEF1-4AC9-B554-036AC5D30C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d865edc1b0d93543738eeec480dc29eb5a24808","datavalue":{"value":{"entity-type":"item","numeric-id":1367169,"id":"Q1367169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$ADB1BADA-5169-45AF-8D5C-95DC6707D774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62e967816953cecad41268e715794a55d56323d","datavalue":{"value":{"entity-type":"item","numeric-id":3577833,"id":"Q3577833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$4F225509-4073-46A0-9C5C-4A62185DD4F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92d2d426786f9b03ff4fc4b322991d027851cf5b","datavalue":{"value":{"entity-type":"item","numeric-id":911323,"id":"Q911323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$18D0E5DB-6577-474D-B20E-2D041485D2F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"635e179f104df43c07c39243b0374fb69763997d","datavalue":{"value":{"entity-type":"item","numeric-id":1356410,"id":"Q1356410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$A91F7632-8A22-4B14-9A76-0CF42597C866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b43e3e48b388828a7b8aa17c3f81b7b754c93ecd","datavalue":{"value":{"entity-type":"item","numeric-id":773621,"id":"Q773621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$FE269644-9E0B-406C-B6C2-BB8C8B44D0CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1868b3e40e91fd44c69a4a5e68f7191fbe6e09b8","datavalue":{"value":{"entity-type":"item","numeric-id":709325,"id":"Q709325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$911CE750-2F57-4077-B683-4C80D686B72F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33959e8c3fbe7080f98305389592daf8f06321e","datavalue":{"value":{"entity-type":"item","numeric-id":5634016,"id":"Q5634016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$05743E0C-26DC-4558-B3F2-FE4DFF8AFC48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9001c5ea90a954557f0ac10357c47c6f8c94b6a","datavalue":{"value":{"entity-type":"item","numeric-id":967317,"id":"Q967317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$B1F13E52-0A9D-449E-A4F0-707FBDDB1B97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3104ef1344a4dab22c02d4743e50ab0ca41ae02","datavalue":{"value":{"entity-type":"item","numeric-id":5263816,"id":"Q5263816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$46940EA5-BC74-466B-A203-9A17052C8C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"203054b8d96eb6037793555d65cbd877d9154668","datavalue":{"value":{"entity-type":"item","numeric-id":1850536,"id":"Q1850536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$739F28CA-71E2-499C-8AB3-286F1F7B860C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be3c5a8818c4c46851df63da12a053a069982e14","datavalue":{"value":{"entity-type":"item","numeric-id":3445775,"id":"Q3445775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$D2D42EAB-D625-493B-8B9B-0E7DF9B17BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b6f1908cd1b59aca2987eca70004e6f715c871a","datavalue":{"value":{"entity-type":"item","numeric-id":5300005,"id":"Q5300005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$98AE8E73-B60B-47EA-B7BB-F54F495B9ADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3783682dd8eef5935b8343c4776479956c89028d","datavalue":{"value":{"entity-type":"item","numeric-id":2921734,"id":"Q2921734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$921A88D0-2EF7-48B1-AF1C-7039A2647AA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb02d1530df8d4822ba9988c3f071a8b03ac3250","datavalue":{"value":{"entity-type":"item","numeric-id":2482884,"id":"Q2482884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1744983$542C9135-E240-41D8-A0A6-E972EB0022A6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"20b850b79fc0a0642ea8533688773710a326fac0","datavalue":{"value":"https://doi.org/10.1134/s0081543817090139","type":"string"},"datatype":"url"},"type":"statement","id":"Q1744983$DEFB1247-779F-4198-A721-99069C19AA24","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08600221a4d47fac0cfad979667c731f8a57da04","datavalue":{"value":"W2789978531","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1744983$267E26C9-2FB5-4367-B52D-D7B34B6F6F2D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9d13b49c4e0e31c263e84d43d69e5a974101267","datavalue":{"value":{"entity-type":"item","numeric-id":685602,"id":"Q685602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4edf7db80d629e1125f8f2248af5645474be38ae","datavalue":{"value":{"amount":"+0.7741842865943909","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":"Q1744983$F57F2324-4EA9-40B8-A2DA-E3A815590577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ef715061fb9af0b567f00940891b8fff8af4a0e","datavalue":{"value":{"entity-type":"item","numeric-id":1328583,"id":"Q1328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afc51cced885c3c3b0fd86396962d483d2bec10f","datavalue":{"value":{"amount":"+0.7721367478370667","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":"Q1744983$DAC42AC7-2A72-4457-BD54-D4D35D7055E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93f652d2c762f6f68c426726fefe003c77144046","datavalue":{"value":{"entity-type":"item","numeric-id":3599118,"id":"Q3599118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71b9fef34750a1bc8da6caeaf22610665b0b76c0","datavalue":{"value":{"amount":"+0.7645496726036072","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":"Q1744983$BDBF9E2E-868D-478F-912E-103481257F98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eef7034741345ea5af3bc01f92aefc3b3705b799","datavalue":{"value":{"entity-type":"item","numeric-id":3508568,"id":"Q3508568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb730eee1212895dd2d1cdc626ba67689803b8c2","datavalue":{"value":{"amount":"+0.7602199912071228","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":"Q1744983$1B38AD31-5EB3-4217-8000-EBF38D4EB072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adad9a2ed761b858b31ed067d13ac7b4f855d26c","datavalue":{"value":{"entity-type":"item","numeric-id":5056146,"id":"Q5056146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"437eb8e3a0b9585cab6a730bb5c0922a502a55ce","datavalue":{"value":{"amount":"+0.754627525806427","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":"Q1744983$A4408ECA-9DBD-4985-BDA7-456A72170304","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1744983","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1744983"}}}}}