{"entities":{"Q2488233":{"pageid":2498976,"ns":120,"title":"Item:Q2488233","lastrevid":72740562,"modified":"2026-04-14T07:20:43Z","type":"item","id":"Q2488233","labels":{"en":{"language":"en","value":"A short proof of the NP-completeness of minimum sum interval coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2198563"}},"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":"Q2488233$056800E4-9F2E-4FC8-B2C5-2A451F7CE898","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"700901d3cfe25a8d7b930093f193fc0977de7a34","datavalue":{"value":{"text":"A short proof of the NP-completeness of minimum sum interval coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2488233$A66C4B5B-4A6D-4749-A2E9-E515E42AA765","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2312fbbf6896c2fdf8e433458d80a975bc178509","datavalue":{"value":"1067.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488233$F2B3C666-4C8C-43BC-94A1-431BDD122758","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d363cb3f47628078b3b27b047f92db7ec1a5ada","datavalue":{"value":{"entity-type":"item","numeric-id":300459,"id":"Q300459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$E8713B62-600B-4377-B290-0525610B148F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$D05D5856-B127-41AF-8BE5-62D0081CC537","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"aca40131a4b359e0412a5ddeceecc24f8a40f1e6","datavalue":{"value":{"time":"+2005-08-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2488233$866C39BF-0BE9-47BA-9F91-E279470500DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488233$60BB7504-4B08-4109-8D60-CCB520DDB251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488233$DF7D3DA4-A457-4BC2-998C-886D52DDAF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488233$5101CBE5-343C-4F66-BDF8-91AFFD19F0DD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0fc730a49806f02c3e426fcd5b8e859482cf3687","datavalue":{"value":"2198563","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488233$0A53C8D2-BC20-42B8-9D8D-45D6A95DE583","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da67da54e89e7c80f20f3f95c3ceec18bb927753","datavalue":{"value":"Computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488233$AAACE36B-7D9D-495B-B230-C85CEB670C3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c7e0e43b7e7433e67c7d5ddce19350cb7a9382e","datavalue":{"value":"Graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488233$94A6F9FE-3558-4696-90D3-243F9337D496","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c85231a82396f49cfb5eccda5cfda757d22b9c81","datavalue":{"value":"Minimum sum coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488233$EB9A7CF2-57B0-44CE-A731-232B58AE6920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a57075e0885acc12de56ab32fb3cd2503cd9b437","datavalue":{"value":"Chromatic sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488233$35F9FD65-2C67-4F60-A873-F126D2961E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"077ef0ffbba1c3b03db2983dd9c5c61094c7068a","datavalue":{"value":"Interval graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488233$5557542A-B0E9-458F-B69F-47AF0A0A9591","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":"Q2488233$78919808-AF9E-4A2B-AD53-B33912C5ADFC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6f4b221bc8e3903aa5e20e3b1bbceb634d59093","datavalue":{"value":"https://doi.org/10.1016/j.orl.2004.07.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q2488233$6F9BF77D-7BEB-4B68-B60F-3F2ED163DA01","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"460c301d342a50f521860edcba3c78c9b336b1bd","datavalue":{"value":"W2003902428","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488233$4D1ED283-B47B-458E-9C80-1BE498728A25","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"330c5a3600c2ca6f87aacf49b4c7ee7ec19cc856","datavalue":{"value":{"entity-type":"item","numeric-id":1383159,"id":"Q1383159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$B46449C4-BF59-4562-AD79-4AC15692D029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72c774310765c7ea8629519fdfcb607c2e8001d6","datavalue":{"value":{"entity-type":"item","numeric-id":4209269,"id":"Q4209269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$86D55012-2790-4B20-BA13-8DD4C346E430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8966655ecbb1863d7d15b1de7a7a366acdd2bc41","datavalue":{"value":{"entity-type":"item","numeric-id":3964622,"id":"Q3964622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$B5441893-6F4B-478F-A3E6-AACCC9EEA3EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60a4af5c5d81357caef23707135c67cb613d6cb2","datavalue":{"value":{"entity-type":"item","numeric-id":4538085,"id":"Q4538085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$A07C41B4-FA85-429A-945D-30FDAD610D6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a577e7face5dced619fd7aa68217e879cec54ef","datavalue":{"value":{"entity-type":"item","numeric-id":1774775,"id":"Q1774775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$F4A651BF-8D0F-432D-B2C2-0F1EACFE44B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43e80cd8930783db35421175d1a15c577f7fd3d3","datavalue":{"value":{"entity-type":"item","numeric-id":2816030,"id":"Q2816030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$894E4379-EBF9-4CFF-A6A1-60AC485661AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee56f0b2d0fd8ca1d2d688b07cba393dcf29565b","datavalue":{"value":{"entity-type":"item","numeric-id":4268880,"id":"Q4268880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$70FAFA62-D49E-4C7B-ABBE-F4E86A641C07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c086e5163977a91fa521aabcbebaf77d9c4c7c1","datavalue":{"value":{"entity-type":"item","numeric-id":3900112,"id":"Q3900112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488233$21294F4E-D64D-46A6-9881-30FA9E30BD82","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fddac371429755a9f9e99edd9681eb5019ec8a0b","datavalue":{"value":"10.1016/J.ORL.2004.07.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488233$8F72C208-001A-4528-B30F-A613526E6FE9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"512291d04b45cd0bec9caed0fc942ecb2a31af64","datavalue":{"value":{"entity-type":"item","numeric-id":1827686,"id":"Q1827686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01696693320954d4eaf4efded7ee9bba618921bb","datavalue":{"value":{"amount":"+0.91931236","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":"Q2488233$6FE4050C-C99E-4DA6-B56B-5A9245EDD218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0132464d5f557d90391fb23a45ee79652722d1c8","datavalue":{"value":{"entity-type":"item","numeric-id":1277392,"id":"Q1277392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74fc83a536bda3f604deb8c6ca8120fbf44864de","datavalue":{"value":{"amount":"+0.90623283","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":"Q2488233$A2A8B961-40A6-4497-82D3-1594AF8C30E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d087d27b8af290b4c481fb9856e97af8cd1075aa","datavalue":{"value":{"entity-type":"item","numeric-id":2883634,"id":"Q2883634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce35c7198b400a1dbce86130ef9ccfed56bd7702","datavalue":{"value":{"amount":"+0.90597236","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":"Q2488233$2414F893-159F-4E7A-903E-9587B237F391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60691efdbd0b46a267edf435a1dc34c17650d520","datavalue":{"value":{"entity-type":"item","numeric-id":2410252,"id":"Q2410252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a59b020940b00fa97ea2b8d04228834284953a8","datavalue":{"value":{"amount":"+0.89587265","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":"Q2488233$41B9EC56-0591-4AA7-909F-CFC18B3F3640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e38582f30f49405c18dc8dc4ac6ddf7a614d92db","datavalue":{"value":{"entity-type":"item","numeric-id":1028432,"id":"Q1028432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45fde1a1ec609dbc09b2e35a179cee5dd306c696","datavalue":{"value":{"amount":"+0.8948267","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":"Q2488233$235AFCD8-2638-482F-9B24-C69B06CE7049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4257c58e403235393cff7e615f1bd01b1567b06","datavalue":{"value":{"entity-type":"item","numeric-id":3060771,"id":"Q3060771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e26d15506de1148e1cd4a5175283b9d583081c09","datavalue":{"value":{"amount":"+0.8863769","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":"Q2488233$1AD7A948-6E64-4AB3-8666-A437B862F79A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcbe4807460ff6856c8e78125040e92a7c46ab06","datavalue":{"value":{"entity-type":"item","numeric-id":1662109,"id":"Q1662109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e26d15506de1148e1cd4a5175283b9d583081c09","datavalue":{"value":{"amount":"+0.8863769","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":"Q2488233$51550750-44E5-4341-BDE9-16D60E6900F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"addde04852f5da789b0cf824cda5d4099b664607","datavalue":{"value":{"entity-type":"item","numeric-id":2003584,"id":"Q2003584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"885a162b2a5d78988304d1832d6b7121f864aea3","datavalue":{"value":{"amount":"+0.8826261","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":"Q2488233$762E6E84-A843-4E64-8355-777A6CC007B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b5ed2ad8e9aec2e1a280cb79d0339a40003cc6d","datavalue":{"value":{"entity-type":"item","numeric-id":415283,"id":"Q415283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb7d0ea027876d2ab9fb463ea8a887ff1f511e36","datavalue":{"value":{"amount":"+0.88024145","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":"Q2488233$B71B8C79-ABB9-4973-AA0A-49C8A92FCE1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f358ec94a5693ec4cf902735d7a56526c03ce23d","datavalue":{"value":{"entity-type":"item","numeric-id":3596703,"id":"Q3596703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb7d0ea027876d2ab9fb463ea8a887ff1f511e36","datavalue":{"value":{"amount":"+0.88024145","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":"Q2488233$ABDA2D1D-3330-4D7B-B5B5-B5196B2471D4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A short proof of the NP-completeness of minimum sum interval coloring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_short_proof_of_the_NP-completeness_of_minimum_sum_interval_coloring"}}}}}