{"entities":{"Q2446103":{"pageid":2456846,"ns":120,"title":"Item:Q2446103","lastrevid":51978761,"modified":"2026-01-20T16:31:13Z","type":"item","id":"Q2446103","labels":{"en":{"language":"en","value":"Hardness and inapproximability of convex recoloring problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6285602"}},"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":"Q2446103$EBB4B4AA-5246-4DF6-9A5E-3106AB34AE44","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"19492231f119851b13a4b86ef3355c405bb20b17","datavalue":{"value":{"text":"Hardness and inapproximability of convex recoloring problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2446103$606A8350-362A-418B-B778-B485E612C0AF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"86ec8820ed7324eee5f5e0c077885ad22e72c04e","datavalue":{"value":"1331.05203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2446103$A342D6B7-ADCC-44CE-A0FD-47D77624E4EA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7245987aba5af8ec93b255be697761df1f51ae8c","datavalue":{"value":{"entity-type":"item","numeric-id":499365,"id":"Q499365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$0ACDAB6C-B759-4444-8341-0297C221189A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bb11a30272922b8f5b3dfa43ee6cbf89b1efc65","datavalue":{"value":{"entity-type":"item","numeric-id":1932474,"id":"Q1932474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$31B271CB-951C-466F-90A7-23E2882239FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00dcd34d2a42ffd4c9646545f08dca80da5e12dd","datavalue":{"value":{"entity-type":"item","numeric-id":590171,"id":"Q590171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$B1A3686E-907B-4518-877F-D70785C3872D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e9df5e8cc9f676aae4fa82e04cd74b4e4c6efa1c","datavalue":{"value":{"entity-type":"item","numeric-id":1392563,"id":"Q1392563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$A42C958C-659D-499D-AB52-C5AF63B04F16","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$CB3200C6-FE5A-414B-AD92-8887250BA401","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a3c251b63516e63161db6918c2e83c80c7676385","datavalue":{"value":{"time":"+2014-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2446103$A55BCA88-14A6-4AC4-8173-D7B0E16A350A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2446103$B56B34E9-EBEC-4D57-AAB8-5663E5838FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2446103$1C186289-AEE5-495A-883F-FBB62251C820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2446103$A9023610-38BC-4566-88C6-1ADD6AE323C3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"baff4373fbdaafa88f4aedf8b8cf82c4ebee367a","datavalue":{"value":"6285602","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2446103$E2EB0115-425A-4282-B93D-1A6A67FB42C2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3711b396d7875734ce4154301cd883105070557","datavalue":{"value":"convex recoloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2446103$195845E5-9EFF-40BB-8B7B-4AED27F1A523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2446103$60670E99-C642-4E3A-BA11-EE2B507C2516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51f95efbd0445c23f397467c5e509da28dd67bbc","datavalue":{"value":"inapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2446103$AC7F3353-878A-447C-A7C1-520CF4E3A696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2446103$828A6B55-18A4-4A90-9107-55B5E29DF1A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b19555075c5893409d350f9eac7df07490a7006","datavalue":{"value":"grid graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2446103$7A947499-6811-4BE4-9ED4-812C9F080940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4e017c3e6a9aec142e4003cef4dc3e8890a19e1","datavalue":{"value":"\\((q,q-4)\\)-graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2446103$0E84B4A6-2AA7-4200-A15B-94E893B6E785","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":"Q2446103$E8F9802A-DCE6-482D-8F64-A680E4399290","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2070b6b7fe9f222538de3c6d52cfa5b8b3d7cab1","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2014.03.017","type":"string"},"datatype":"url"},"type":"statement","id":"Q2446103$380A0470-D659-40C2-A3FB-BAB3A331FBE9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f57a0f95f725fc09b5a1c443f40177f250751e14","datavalue":{"value":"W1971028618","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2446103$8AE63451-B269-49A3-940F-0E21DCE64AC0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2d06f526300db7e0a42c270317b15ba36d696da","datavalue":{"value":{"entity-type":"item","numeric-id":2944511,"id":"Q2944511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$FA74282B-F58C-46C2-B316-A4CDF67E8D01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bd9d97c0e27af45e022519d1248b869d9707949","datavalue":{"value":{"entity-type":"item","numeric-id":1392556,"id":"Q1392556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$809BDBF9-C16D-4EAD-BB58-E7AA49EC3935","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76394e4abf8b245e8e49003c88e08764c6f19a93","datavalue":{"value":{"entity-type":"item","numeric-id":927405,"id":"Q927405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$DA241896-88BA-4FD6-8C3E-2218B454CF82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12fb817e524c8a927486a4021b58019c769a2d51","datavalue":{"value":{"entity-type":"item","numeric-id":639283,"id":"Q639283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$84473185-DE9D-4C36-A742-380037FDDC32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$772B3768-95BC-4238-B278-D2198C10F7A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e7d55c79e386567a77b17f39d9a0366a21d1d5e","datavalue":{"value":{"entity-type":"item","numeric-id":4925275,"id":"Q4925275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$3EDC5E11-511F-4AED-A467-81E11FED857A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"764c27b944c3de212778f8de18e0417d04ec2856","datavalue":{"value":{"entity-type":"item","numeric-id":3608833,"id":"Q3608833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$77D23DFE-877A-4312-9C07-F81EF7A6143A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f66b4844bcb79a520b665f58fdec673994d537","datavalue":{"value":{"entity-type":"item","numeric-id":4393480,"id":"Q4393480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$9D60CEDA-481F-4CBB-8488-F22E83DFDD94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$6289745A-84C2-4F62-A308-AB6D5CCF711E","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":"Q2446103$B87ADA14-3ACA-4002-B364-7C7ECA191251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"280066d459fcc4230be7e309c1901901385f909e","datavalue":{"value":{"entity-type":"item","numeric-id":415283,"id":"Q415283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$1C3700A8-65A2-44DF-A71E-558B13E0ADEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ed03b3ca3123610e5592de0135381af8b4e36b","datavalue":{"value":{"entity-type":"item","numeric-id":5323087,"id":"Q5323087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$DF2E6CA4-B3AC-4477-9186-1E1924806D4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3b2998788fd5c6bb689ab64483e3a026a3e293a","datavalue":{"value":{"entity-type":"item","numeric-id":1183332,"id":"Q1183332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$8078AF7F-C30F-4A9A-98E8-351F885923C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60d42535f43ad050e582a19dfea8b7a35eeb602a","datavalue":{"value":{"entity-type":"item","numeric-id":2448880,"id":"Q2448880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$C47D5E54-C5EF-4144-B636-2BEE9A181FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff891f450486512d7582e2236ee9e2d3bcc00754","datavalue":{"value":{"entity-type":"item","numeric-id":2643731,"id":"Q2643731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$FE167E5C-14BC-4415-872F-D44394D80016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763010867f4d747d938db2b8db427628ca83eef6","datavalue":{"value":{"entity-type":"item","numeric-id":931727,"id":"Q931727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$5FDD19A6-51F6-4070-8C7D-0C7B9197918A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffeb5eff20708e2c1fec31e4f5e41f76b3c24c88","datavalue":{"value":{"entity-type":"item","numeric-id":3189026,"id":"Q3189026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$3E79862D-21F7-41AE-B917-0E32FE463390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df707866d55069e9c624e86b2f3ac5960ac5212d","datavalue":{"value":{"entity-type":"item","numeric-id":1152215,"id":"Q1152215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$210822C1-2361-4F7B-8580-49A1AB24CC72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b63139d2551816659aa056c8e5779ecf1724996","datavalue":{"value":{"entity-type":"item","numeric-id":3502673,"id":"Q3502673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$121521ED-C920-47B9-9EA7-F7412E8D369A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d5cfedfe66a3b5d774d6c8fbd31b828323bdab","datavalue":{"value":{"entity-type":"item","numeric-id":4527015,"id":"Q4527015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$C2A30CC0-6DA9-495B-90D3-43B333A26CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1348692f69417a049e566bde26aa400c6a92bfc","datavalue":{"value":{"entity-type":"item","numeric-id":2379996,"id":"Q2379996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$8A049BB1-31E9-4BD5-86C6-184E4CD2CA95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a20d09513baf32113955ba3ecf79c8e2d6ab34f2","datavalue":{"value":{"entity-type":"item","numeric-id":3512428,"id":"Q3512428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2446103$9AFC5138-94B2-471D-90CB-AD37F5ACD032","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"245f83b130d84d20a95a5b365b43393120021b41","datavalue":{"value":"10.1016/J.TCS.2014.03.017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2446103$D33EFD36-1202-42FB-8A1C-AFF72665847E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7be9c148ed780bcd15adf2aaeacfb8e6951e40e3","datavalue":{"value":{"entity-type":"item","numeric-id":4925275,"id":"Q4925275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5705363083fdff0f5136bd51d4ac0b7ac6ec705","datavalue":{"value":{"amount":"+0.9799991846084596","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":"Q2446103$49B1E2D7-3A17-4AF6-9BF0-6C0177E9651A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b26989340011407bb0036fdb17bbcf65f93a3b24","datavalue":{"value":{"entity-type":"item","numeric-id":2184691,"id":"Q2184691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92d3ec17af04ce6efbd15abf7bec490e8b7e492c","datavalue":{"value":{"amount":"+0.90753173828125","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":"Q2446103$2C708721-0BBE-4AB2-BDEF-30B085BA82BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fab1cfa241d95d15564734df15a81ee1fee31ed0","datavalue":{"value":{"entity-type":"item","numeric-id":2413156,"id":"Q2413156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93a7ea374faf17ca0db780bf79cc7d41c85bec95","datavalue":{"value":{"amount":"+0.905749499797821","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":"Q2446103$9DC2DDEB-825C-4694-833B-0BF95AF106AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de6d612a6ac8a8fa6352d56c875b4e6face6412c","datavalue":{"value":{"entity-type":"item","numeric-id":2798241,"id":"Q2798241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"346d573ea360faeaa473c0423ebaa69d74e77dcb","datavalue":{"value":{"amount":"+0.9051227569580078","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":"Q2446103$B6FC79E1-00D5-4BA0-8A18-0157DE316C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cba03de2f60bdb87ae850ed611d9ab8c9ad34cda","datavalue":{"value":{"entity-type":"item","numeric-id":1647830,"id":"Q1647830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2590bb257e02bd2bd0ee11c6f644c137d3cb0090","datavalue":{"value":{"amount":"+0.9028194546699524","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":"Q2446103$F5C2DEE8-AB85-4475-9C02-4D17A767D6AD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2446103","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2446103"}}}}}