{"entities":{"Q1062924":{"pageid":1073676,"ns":120,"title":"Item:Q1062924","lastrevid":66062844,"modified":"2026-04-12T07:17:10Z","type":"item","id":"Q1062924","labels":{"en":{"language":"en","value":"Analysis of heuristics for finding a maximum weight planar subgraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3916045"}},"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":"Q1062924$D8E378C9-87F7-4BDA-BD47-81579EF8E283","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"17ed18bac0d5029543892337093d5784ca401a4b","datavalue":{"value":{"text":"Analysis of heuristics for finding a maximum weight planar subgraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062924$10FE324C-4169-440E-A279-160E63ACDDBD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e08c81f4719f55520f07dd313ca7daf4b74830a9","datavalue":{"value":"0573.90093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$A914DFAA-EAAA-4B32-B493-F2C98D0FFF4A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d8e4135f9b55bc20b9b06f38fc2d7a076916a5dd","datavalue":{"value":"10.1016/0377-2217(85)90288-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$3978BB01-BF08-483B-8A68-8CC7EC2B6198","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$C51778EA-8B8B-48F4-9600-848FFED558D8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1062924$B467AA5F-2B88-4913-9DDE-65052A822765","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"422d156c1e43ca126a9e70556c8d3ca5686c3ae3","datavalue":{"value":"Three heuristics for the problem of finding in an edge-weighted graph a maximum weight planar subgraph are considered in this paper. For each of them, the worst case ratio, i.e., the ratio of the weights of the subgraph chosen in the worst case and the optimal one, is computed. A random model is also studied to show the 'average behaviour' of these approaches.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062924$62EFBE30-00E8-4242-87B0-49D71DD00D02","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$104B3CF6-342D-4778-8630-E66C2EC6DEB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$1932F3F9-269A-4DB1-84EB-884EC7EA47A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$554FF164-5497-4211-9D73-BE0D0070F9CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$1D9128F8-3C06-4334-8315-E4905F6894D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$39A5F3C7-9008-4FC3-8390-8D3EA6F06B48","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5cff5967ef110cb6b1c88a5a36e4a52a8d009e66","datavalue":{"value":"3916045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$29A638C1-582D-43FB-89E6-954459493FB9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"725039e049fcdd95b8332901db04d287b64101cc","datavalue":{"value":"polynomial-time heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062924$2F606CBC-A694-407A-89A1-000F028CE770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e31935d343f25631518799349b31ff89b05e631","datavalue":{"value":"facilities location","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062924$2302D2D8-152F-458C-921C-A96825652B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7680d75907fb855f1967dae63c7b35990c10ddac","datavalue":{"value":"edge-weighted graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062924$23DE81BC-22BD-41E2-A510-3F95842D3B68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43af6347817767ef80dbc9d05e2bd3158d3a843c","datavalue":{"value":"maximum weight planar subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062924$C0ECE37E-1B9F-4ECF-97AA-89A65872BB2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c4297c2a61aab657a69df86d905092ef80bbdeb","datavalue":{"value":"worst case ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062924$7EFBC7E2-323D-4ECC-A5FE-24BF0948FE11","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ac6079b2082bbed271309fb2d51b5b4c5dd28d8","datavalue":{"value":{"entity-type":"item","numeric-id":247119,"id":"Q247119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$F806A22D-1C13-4F33-BE8A-DEE365D02BAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8009c976241ee03d1e03b4dae561a3c344c0394e","datavalue":{"value":{"entity-type":"item","numeric-id":486407,"id":"Q486407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$6E58349A-1A14-4160-9546-66726F76E95C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$7665BA07-D7B3-4234-9480-895740090E9E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"89da44d991bca604b3883c31e3d7f2a2430c9f66","datavalue":{"value":{"entity-type":"item","numeric-id":348641,"id":"Q348641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$BD685531-1613-484E-AA5A-C8CE52D7C449","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":"Q1062924$E39311AE-FC4F-458D-BD64-18BB0285D4E9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fc254f85ea92139b1c40195a152921696a41627c","datavalue":{"value":"https://doi.org/10.1016/0377-2217(85)90288-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1062924$AA1B54E0-9543-4153-A35C-92AB5320AABB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a40751c5be6900506b5f6d93489bc95cf5fa257","datavalue":{"value":"W2075838454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$848B44E0-995A-4C67-AA01-3E9545135CEC","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"30685d34f22ae770e4c9baa49eeefe5ebd3aecc8","datavalue":{"value":"Q56324168","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062924$A0B950D2-90A4-47D6-9DF0-C88F016F76DB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c5725dd1681571d61e6f93ee7b036b2585b942e","datavalue":{"value":{"entity-type":"item","numeric-id":4124643,"id":"Q4124643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$93CF9E50-5F93-4D11-B0BB-60CAC18A2106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1c723c85ec0475073d4f60fd21960a4bd17a3ad","datavalue":{"value":{"entity-type":"item","numeric-id":3693214,"id":"Q3693214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$F550796F-7BCD-482B-88C5-FC1D01AA9177","rank":"normal"},{"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":"Q1062924$D9006452-9C63-45F3-9B6D-2EBBEDC9BB91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9e82f378645b1b9d2cb51da2d39e946c18e4b4b","datavalue":{"value":{"entity-type":"item","numeric-id":3956129,"id":"Q3956129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$3E441184-0726-4A41-AC9D-0C9277C6CCD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$D47BA71F-61AA-416F-8488-D18A4B27FAEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$F4239CDB-C615-4D07-A1D2-7EEE4283FDF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2533ca9b57f93e7251fd366784646baeb10e1a3","datavalue":{"value":{"entity-type":"item","numeric-id":4174528,"id":"Q4174528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$61AE0336-278B-4429-9F06-A0BC727630B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71562bd2025d3567428b1caf5e1cd4341880622a","datavalue":{"value":{"entity-type":"item","numeric-id":3866146,"id":"Q3866146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062924$FC0DED68-EC5D-462E-B205-C750467637A6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef2075d50005c8c26dee52089ee40897e1a50858","datavalue":{"value":{"entity-type":"item","numeric-id":4886062,"id":"Q4886062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ce46ce5eeb36df70d980a13854fe1d12237e865","datavalue":{"value":{"amount":"+0.8836584687232971","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":"Q1062924$0B519B5A-5155-400D-B048-C1FA56E9044A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bdaa508d92a9f660d4dc8f3650e85d8317d0d1c","datavalue":{"value":{"entity-type":"item","numeric-id":1400892,"id":"Q1400892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2cad6bd9761ba6945abb0777163b6aaeab99303","datavalue":{"value":{"amount":"+0.837411105632782","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":"Q1062924$18073F68-9826-424A-9848-12FD1FF27F60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d00a6dc8d8770c0286fe5798ab8e5f0751444cc6","datavalue":{"value":{"entity-type":"item","numeric-id":4354090,"id":"Q4354090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c67943e975548dbf6fd6ae3fd38166cb7b02be2","datavalue":{"value":{"amount":"+0.8260257840156555","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":"Q1062924$342634E7-481C-46C0-9D78-34F2CF903AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2980c07f0a2328f50842e1c72977a325d681977a","datavalue":{"value":{"entity-type":"item","numeric-id":4831415,"id":"Q4831415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01459dcaaa2a76f5350555fb573bc2a0620e898d","datavalue":{"value":{"amount":"+0.8188894987106323","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":"Q1062924$8382C4B4-403C-410B-AF66-2829E04179E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbfa5f1da6ea35fe867d6e8175b98f495bcc4334","datavalue":{"value":{"entity-type":"item","numeric-id":4216139,"id":"Q4216139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"600e68a4a75dfe21c008e7109355108f0d473d3b","datavalue":{"value":{"amount":"+0.807076632976532","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":"Q1062924$1FB56A9F-6CCC-4FF8-B12D-6FCA0533FB25","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Analysis of heuristics for finding a maximum weight planar subgraph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Analysis_of_heuristics_for_finding_a_maximum_weight_planar_subgraph"}}}}}