{"entities":{"Q3763600":{"pageid":5793506,"ns":120,"title":"Item:Q3763600","lastrevid":51798158,"modified":"2026-01-20T02:26:04Z","type":"item","id":"Q3763600","labels":{"en":{"language":"en","value":"Improving the performance guarantee for approximate graph coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4020494"}},"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":"Q3763600$7DE07BBF-973D-400B-9EB0-F1CF53BF4754","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"917128bcf0f09038cb29dab0c2f95220d0a612ab","datavalue":{"value":{"text":"Improving the performance guarantee for approximate graph coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3763600$D26D108D-D2A9-4146-8E83-17ED69F968C9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"667acb562b4c9a432c43982c8d7a014d34bd73ba","datavalue":{"value":"0627.68057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3763600$EA9A8D99-2FE4-4D2A-90C3-6AB1E9D41B13","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72783e2b27427b4d8720698c910f0d0e891ad7e5","datavalue":{"value":"10.1145/2157.2158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3763600$1CCA7915-15E8-4EC0-98BB-5A779C7ACA18","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a028a6348dcfc7b43c17e257a75b67ed9a2b7db","datavalue":{"value":{"entity-type":"item","numeric-id":178716,"id":"Q178716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3763600$D5254F48-9F1E-4555-AF6C-EDCB046D22D2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f12bfc80fe4a431c556e028f5134a217234a7cc4","datavalue":{"value":{"entity-type":"item","numeric-id":63915,"id":"Q63915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3763600$4F41B993-412E-40F5-BCB2-B52EC203E423","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q3763600$7F94114A-AB4F-4995-AA6E-B72F8C91C759","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3763600$E0ACF7A4-66E8-4915-846D-CE2E3205414E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3763600$2CA0EDD0-C003-4C3A-A12A-EFDD90CEBC08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3763600$85BDDBBD-AF2C-4833-B392-B632FF4862C1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f7200f3ddd51e95d41872b430ad0639cba9c2282","datavalue":{"value":"4020494","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3763600$0C97852C-7829-42CF-AC90-CA27D3069970","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3763600$A84FD505-6F41-4CEE-9B20-295D5B60B404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf0cbd0af7eae967be7b9e298165125d3f799a99","datavalue":{"value":"performance guarantee of a graph coloring algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q3763600$3CB2437D-1D14-4B8F-8D7A-BA20198A29AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f0372b709aa97e849bb7c41513a3127bfd7086","datavalue":{"value":"number of colors","type":"string"},"datatype":"string"},"type":"statement","id":"Q3763600$6F5D0249-3095-46A7-A69E-E8B65BC11811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q3763600$B51B26DB-DB43-4FCE-9771-99607A69867C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7321e9cc7f856900fc45d86206df7f382a3fd6fe","datavalue":{"value":"Q29399072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3763600$EFC1D823-40CD-4A2E-97E2-A2AA0CC97CAC","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":"Q3763600$44F80F64-169B-4D0B-9EC6-D7AE4A687F1F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e24bb66a449c3c03a600db81cc8bb2adef5cfb97","datavalue":{"value":"https://doi.org/10.1145/2157.2158","type":"string"},"datatype":"url"},"type":"statement","id":"Q3763600$AFFE4CA7-E4CB-4C3B-A5EC-67BA11184BC0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"817048881c891bc7c85c32a7deda98e0a4d40a8b","datavalue":{"value":"W1982506822","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3763600$5D572D6A-471F-4A83-8801-9CBC11DF4F4B","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"08769f8139191465d846ea10b2d6a171aa9750f4","datavalue":{"value":"journals/jacm/Wigderson83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3763600$944B769F-DA86-4491-A33C-885A3163F846","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cb4637adfb72d03bf3a30e1b5229c51bd50aaed","datavalue":{"value":{"entity-type":"item","numeric-id":911757,"id":"Q911757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b7482a2d9518b2429849948086ddaf009eb2f19","datavalue":{"value":{"amount":"+0.98421985","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3763600$98435562-4443-48E3-8D85-D4E55A381376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a74834b6efb6eb2b8c09a27d335511ee08b08574","datavalue":{"value":{"entity-type":"item","numeric-id":1209311,"id":"Q1209311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a291272d83b25bd7b6b688f45d2ec0b0a92cce0c","datavalue":{"value":{"amount":"+0.9719956","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3763600$060CBDDE-1DA4-43FA-A8BE-CBE1182EF50A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e10010805c93e2a1d11419dd34968a13d03cd62","datavalue":{"value":{"entity-type":"item","numeric-id":5175094,"id":"Q5175094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0c27b6cd36eb0c122fdf640faeb16cb179dc2f0","datavalue":{"value":{"amount":"+0.91593564","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3763600$5C7A4DFF-0EFB-4F55-8C73-1A554C2F90D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2803e5a07fcc4cfd536be4358dfc96be6f071806","datavalue":{"value":{"entity-type":"item","numeric-id":4305670,"id":"Q4305670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b90710466f5ea7d018a59c30d1658265a14bedbd","datavalue":{"value":{"amount":"+0.9155896","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3763600$5F29101C-49C6-48C8-AE5E-4A7238D5E6E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58c90c6c759b271cdd2b0e29f7422d86d1160913","datavalue":{"value":{"entity-type":"item","numeric-id":293395,"id":"Q293395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abb46fb09b0e58e6c65fed71bf1610b28e443046","datavalue":{"value":{"amount":"+0.9126982","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3763600$0E2F798F-BE98-47C2-B383-42D091A16FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b5f65a18b69f8638c2220c2d1c6ccb7c34b685e","datavalue":{"value":{"entity-type":"item","numeric-id":5687263,"id":"Q5687263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7c16e1dcd9168e6df8d79142ff71517ee768b37","datavalue":{"value":{"amount":"+0.9112426","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3763600$889CEFC4-6ADB-4D08-B4DC-8228D1D3A418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f11b83a5e77f2a625722efd05bd1448beaaf98f","datavalue":{"value":{"entity-type":"item","numeric-id":5875482,"id":"Q5875482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"027b017723dfe282061804f47715a166480e0ebc","datavalue":{"value":{"amount":"+0.9079771","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3763600$B6F682C6-0AFF-4751-ABE7-CC86D53ACEF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06962e4c91b7a39e4e605bc4a65d58a2714678c9","datavalue":{"value":{"entity-type":"item","numeric-id":3841651,"id":"Q3841651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8520dba356846256522a3d8ce381c41d7958e6bb","datavalue":{"value":{"amount":"+0.90794396","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3763600$90800C97-0C80-41DF-9587-59BB6ECDB7B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"133f2a27665b825ea48eb47daebdac1df4c98671","datavalue":{"value":{"entity-type":"item","numeric-id":2999347,"id":"Q2999347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26e037eaa45d890197c45253032e6b818cc1b011","datavalue":{"value":{"amount":"+0.9068942","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3763600$B8DB0751-10B1-46B5-90F7-3DECB489349F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3763600","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3763600"}}}}}