{"entities":{"Q4925275":{"pageid":6954857,"ns":120,"title":"Item:Q4925275","lastrevid":91967810,"modified":"2026-06-05T00:31:49Z","type":"item","id":"Q4925275","labels":{"en":{"language":"en","value":"On the complexity of solving or approximating convex recoloring problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6174190"}},"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":"Q4925275$F06B6A88-15AC-407D-8C5C-BCFC0D30BB83","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a6c45c6e3ecaba273f54521ff014747b8e323b35","datavalue":{"value":{"text":"On the Complexity of Solving or Approximating Convex Recoloring Problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4925275$08C370E1-7C25-4AE6-9F16-734AB9886B75","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"19e9b9fa979289f8b7e1fbfaa804342f4e4d7993","datavalue":{"value":"1382.68100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4925275$E36CE501-13D3-4F5F-929B-77075AA71E91","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8f4e9f62fd9b82139ec1ba01c19ad608365ff349","datavalue":{"value":"10.1007/978-3-642-38768-5_54","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4925275$E6F75683-AD91-4505-91A5-B6DBD6C39172","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":"Q4925275$C1E7795E-257A-4AD4-986E-9E8231DA7F69","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":"Q4925275$6C97DB10-6DC5-422F-87C7-810367BA9243","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":"Q4925275$0F642CF8-CDFA-4A87-A22E-4B3F9C7FE6A9","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":"Q4925275$1FED7A7B-1D32-4F95-8EBB-81D970C49A22","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4925275$AE0CB31C-9F76-486F-97AE-9580523F151C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8f1333f5ea32121d60563094ddcc091f8ab3e533","datavalue":{"value":{"time":"+2013-06-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4925275$FCF4BE91-1B12-4601-B561-9BFC8895F27A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4925275$17D90D0B-D945-4944-87E6-A04E661B6167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4925275$6C2E480B-CC23-4E27-B38C-7BED974E3BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4925275$80DD5166-DAC9-44A8-A933-4196F2453E6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4925275$F6DDA3D6-13B6-4D56-82EA-8FDF7675809E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c2d6e0f3e9d29fc2151bfbf0638d0d3ffc12e640","datavalue":{"value":"6174190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4925275$51E81D5A-56E2-4020-A0F4-23E6EDD5FB45","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3711b396d7875734ce4154301cd883105070557","datavalue":{"value":"convex recoloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q4925275$B97AF5CF-EBB1-4B7E-82A4-609E7E7B1E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4925275$1813AAEE-ED99-4171-9729-94B8E713200C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51f95efbd0445c23f397467c5e509da28dd67bbc","datavalue":{"value":"inapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4925275$B59AE2F2-D253-4694-9FE5-F6B88F4CC3F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4925275$EBCD9576-B803-4835-B5B8-636BD55D9148","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b19555075c5893409d350f9eac7df07490a7006","datavalue":{"value":"grid graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4925275$5389A483-3B28-44D2-A1ED-284051EDB47C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ae14706edea88a102ee43da4032c363bf1c64c9","datavalue":{"value":"cograph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4925275$A2D9DD43-1494-4387-BC18-ADFC0182C8B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d27bd4838783c066bf59c43e249203c0d8081cf7","datavalue":{"value":"sparse graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4925275$65836804-CAF7-4D5D-BCFD-E0488096BBDA","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":"Q4925275$998C6E03-BB82-4E37-B19C-D52F61F221D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7b8f9add6fce434c432ca48fcfa2dbc6461f1236","datavalue":{"value":"https://doi.org/10.1007/978-3-642-38768-5_54","type":"string"},"datatype":"url"},"type":"statement","id":"Q4925275$2A17CD32-EA27-4641-8F64-1BCCBADA3CC5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8d4b026800180d683fb74346beaf2dd7a800171e","datavalue":{"value":"W132016661","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4925275$E8C76EB9-8974-462A-AEC2-522A32B752FE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d9da278d0a6f11dbd9541c86986e16134c273b8","datavalue":{"value":{"entity-type":"item","numeric-id":2446103,"id":"Q2446103"},"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":"Q4925275$F2D510CE-AECF-4C83-B5DE-A3A3D0369177","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":"88003ad2433e0a754fcfc374b5676c882cc458fb","datavalue":{"value":{"amount":"+0.9013482332229614","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":"Q4925275$E0849280-C2D2-432F-AACC-B8AC1C9B4603","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":"817282d5cb7956e2aee798fdc0a3998a4d8ee818","datavalue":{"value":{"amount":"+0.900284469127655","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":"Q4925275$A4AED8FD-6151-4BD5-B118-7D141156E3CF","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":"891cba9cef643898eaa324d602e6dc5cef2b9cbd","datavalue":{"value":{"amount":"+0.8979737162590027","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":"Q4925275$B9B9CD9D-A600-4A40-814A-566893D01A62","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":"15ed18d7a2010d984812fd5fe24296efa6ab4523","datavalue":{"value":{"amount":"+0.896308183670044","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":"Q4925275$DE71C262-543C-4AC6-B11A-A1683E6FE0CA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of solving or approximating convex recoloring problems","badges":[]}}}}}