{"entities":{"Q334238":{"pageid":336005,"ns":120,"title":"Item:Q334238","lastrevid":61043451,"modified":"2026-04-10T20:48:26Z","type":"item","id":"Q334238","labels":{"en":{"language":"en","value":"Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6646033"}},"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":"Q334238$F5BEB1B1-3AC3-48A9-8E87-9F1879B630B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"17b798aacfa0a6de52a471af6371e8c750921173","datavalue":{"value":{"text":"Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q334238$AF5C864C-02B2-4AAE-ABA3-31AA5D496D79","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c2e2ae5d5bcccea453dc3b61bcfee2a3a5f7801","datavalue":{"value":"1348.90655","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q334238$78B9C1A4-EA31-4660-AB85-CDB82217B555","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ac60fa2d2adc80c0cfe9b12a6aba5eba7e810aa","datavalue":{"value":{"entity-type":"item","numeric-id":334237,"id":"Q334237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$FF9DB0D5-AFDB-4BE7-89D2-5E1AB61BB901","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1b023419c56b9969f2d98b08637e9b0af86a936b","datavalue":{"value":{"entity-type":"item","numeric-id":199816,"id":"Q199816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$39B70204-69F9-48B4-A074-7065A6953848","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b1e889f7549615622ee2318a0d7c37075384a627","datavalue":{"value":{"time":"+2016-11-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q334238$D91F35AD-AD4F-416E-A059-088C64FB5074","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q334238$52B7854C-5A13-4446-9F0F-C00B8587A895","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a584f0c40bb9dbf5fa41fda69cb91acdce13d8df","datavalue":{"value":"6646033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q334238$47117562-AEDC-4580-BA31-4A4B6C6EA9ED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8afbc852b0241b26196b31e3949fff67213af63e","datavalue":{"value":"multiple reoptimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q334238$7D23A12C-41DD-4393-A174-5A82A6E4521B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae06b3731ea4b2d23fb4471d8c1e97ef2bbe2b93","datavalue":{"value":"gap-introducing reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q334238$DEA9F7D4-D2AE-4D55-AB68-FAA23E2A68C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0819d8c7a78f8a3d73c4059b7fc8dcc3970d9ec","datavalue":{"value":"gap-preserving reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q334238$883F33D1-0BFA-4E01-858E-5BEF2F6F2970","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c562c36759035eb361c19aeaefa854e6a2248a18","datavalue":{"value":"APX-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q334238$51EB2ABC-2A3B-451D-9759-F936AF6288F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21271d86c4238821c55e0537ff1bebd9145b2078","datavalue":{"value":"polynomial-time approximation scheme (PTAS)","type":"string"},"datatype":"string"},"type":"statement","id":"Q334238$A62923DE-D7BE-4603-B5E5-93827909E409","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":"Q334238$6A83BEA0-76D2-42E2-8DDF-E6857AED56FD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"513725e5970ee4f23f0e44efef5590f74ce9782b","datavalue":{"value":"https://doi.org/10.1007/s10559-016-9837-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q334238$C1EC112C-AA35-47AD-B186-6B879B9B15C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6e2a84eaa57c86d5a91b17989ff3bd1b6dfbe84e","datavalue":{"value":"W2406091340","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q334238$83FB9087-B59D-402C-B158-17B044050FBA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c0a13a8417673f45e28aa7499e1e7b9d7bfca27","datavalue":{"value":{"entity-type":"item","numeric-id":3694711,"id":"Q3694711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$1266FAB7-ECCA-43B2-909C-119C3FD7A7CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2610c7d27ba8314328868947db0889cd433897","datavalue":{"value":{"entity-type":"item","numeric-id":3685214,"id":"Q3685214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$F41C61E1-8227-40FE-9595-98B3FC4C706D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f1752c6678262d9ba0fedf23135d543033290af","datavalue":{"value":{"entity-type":"item","numeric-id":2906564,"id":"Q2906564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$3CBC069A-EE14-4177-A52B-3E993CFA0576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c3e497186523c6e1680f272539aee2c43f68f35","datavalue":{"value":{"entity-type":"item","numeric-id":5448637,"id":"Q5448637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$E8117B8D-4633-4D54-A5FE-BAB0ED7D27EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d949d9d42ed88b348ac5c40db320f11fef0b588","datavalue":{"value":{"entity-type":"item","numeric-id":2907959,"id":"Q2907959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$9457DE35-8947-42E2-9628-B2EEB83C1365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dafdfc189679bc368481a74dc58e90bdd442dc8a","datavalue":{"value":{"entity-type":"item","numeric-id":3100925,"id":"Q3100925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$E4B599E9-E4B5-47F9-9802-4FB7EE0F26BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c511bd852b4089d12ce8b654e9616cb95ba506a2","datavalue":{"value":{"entity-type":"item","numeric-id":3009332,"id":"Q3009332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$F5BDDC7A-E5D4-4AAF-889B-FD626A5C5D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc0ff2b40cb90818175a3c67ad7c3b6f416bab63","datavalue":{"value":{"entity-type":"item","numeric-id":464901,"id":"Q464901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$C0918A90-3306-4653-B1B1-717699DDD228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8658e6d71d7258b809c478c332d93b25a4d9b43","datavalue":{"value":{"entity-type":"item","numeric-id":4782696,"id":"Q4782696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$932526C9-2F6C-4850-B719-C905DA1EA250","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf376f2946131481bf0c634e0ff1ff4924c8e63","datavalue":{"value":{"entity-type":"item","numeric-id":4119042,"id":"Q4119042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$48BA149B-7618-4B12-BCD2-ABA513F854B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32e26d900daafb1464f09c1755bc65c087c3dd6d","datavalue":{"value":{"entity-type":"item","numeric-id":3079180,"id":"Q3079180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$B90EC668-27D4-498E-A0C7-9B319F732268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3f32116b14140b15407a7b29e5f718f78a89517","datavalue":{"value":{"entity-type":"item","numeric-id":414457,"id":"Q414457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q334238$5FDE6834-D400-41D9-85CF-3E459A33F463","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b061c3f56dd18a11f23a0bc853ec2f9b9c03d7cf","datavalue":{"value":"10.1007/S10559-016-9837-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q334238$98B274CE-B1AE-4170-B595-CEAF2AE21571","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5b92f045c763fd8b0edb6ecd3c49d9fe292f635","datavalue":{"value":{"entity-type":"item","numeric-id":464901,"id":"Q464901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50dfa40fc022d403c737ed9e03ec9c68e96fdd38","datavalue":{"value":{"amount":"+0.794468343257904","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":"Q334238$222A6D61-658F-4CBB-9087-BDFE6744CEAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d11dc8ab3f939cd900d83810d2f2f7e0b8360d9b","datavalue":{"value":{"entity-type":"item","numeric-id":6163646,"id":"Q6163646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bda78650c539231a97de32f69701dceb7e49c20","datavalue":{"value":{"amount":"+0.7466832995414734","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":"Q334238$9FBA3D3A-0BF0-40A6-95D0-A2A872E5548E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a0380154964293e12482505fd34e4e9d84e8685","datavalue":{"value":{"entity-type":"item","numeric-id":5932643,"id":"Q5932643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b913fb70901bcb6872d44401663fdf39a2ddac6","datavalue":{"value":{"amount":"+0.7451039552688599","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":"Q334238$51E04DCA-2A35-4CB7-B31D-46F5CE17A92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"478c4a24cef9c4d0e0770513d6a20b85a1cb1702","datavalue":{"value":{"entity-type":"item","numeric-id":386899,"id":"Q386899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2070f4099da92190c1718fda8971e706690911bf","datavalue":{"value":{"amount":"+0.7423583269119263","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":"Q334238$DDAED5E8-1258-437E-8C4F-5EF1F22E7165","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edf9e976c15bb31988e451489120ca0222fa4b2b","datavalue":{"value":{"entity-type":"item","numeric-id":5448637,"id":"Q5448637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84488c627586c5b1d05de419761d240789f2b560","datavalue":{"value":{"amount":"+0.7415088415145874","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":"Q334238$C18D533F-1777-477D-B14F-833375E8A418","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Hardness_of_reoptimization_of_the_problem_of_calculating_the_chromatic_number_of_a_graph_with_a_given_set_of_optimal_solutions"}}}}}