{"entities":{"Q1853153":{"pageid":1863895,"ns":120,"title":"Item:Q1853153","lastrevid":71501388,"modified":"2026-04-13T22:40:58Z","type":"item","id":"Q1853153","labels":{"en":{"language":"en","value":"Approximating minimum cocolorings."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856489"}},"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":"Q1853153$A58CF40C-1C3E-406B-A2AE-BBA9B485CCE4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5462d35619e111a4e9a55d5aa322b6fdf53ca0d8","datavalue":{"value":{"text":"Approximating minimum cocolorings.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853153$6DF8919F-3F9E-4521-B399-150ED4C4B472","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eb57c55b8ad5d42b0e4db9805c7aa022b87de6e1","datavalue":{"value":"1042.68091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853153$D29E2205-E9E3-4598-A907-7C350377722D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"16c3cfbe9166cc5c33a7290c99e02c8bd806d1ad","datavalue":{"value":"10.1016/S0020-0190(02)00288-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853153$DE6945FF-423A-4598-A7F1-5CA6923E0F9F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a8874875f41e100f7dd0c90f8e9a202da131938","datavalue":{"value":{"entity-type":"item","numeric-id":259035,"id":"Q259035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$D480B756-B888-4026-A34E-BF6C7D3D2EC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5adf86a269713b0e23511a52caceaa2ff6312793","datavalue":{"value":{"entity-type":"item","numeric-id":190506,"id":"Q190506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$8A756EE7-B5F4-47AF-AD4C-8529E1D9481F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e7118c023ab6f5d58426a596852802cdc9a93a5","datavalue":{"value":{"entity-type":"item","numeric-id":218042,"id":"Q218042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$98DED071-662F-4BA9-A2D5-2840DE2FDC66","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$19B3C1E5-20DA-4CBA-AA59-EB67DFAE26C2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853153$8FAF73DE-4555-45AD-946E-7724B3C36D91","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4ff1bb1fbaa96ed4f44651295aaf10c3931d287e","datavalue":{"value":"A cocoloring of a graph \\(G\\) is a partition of the vertex set of \\(G\\) such that each set of the partition is either a clique or an independent set in \\(G.\\) Some special cases of the minimum cocoloring problem are of particular interest. We provide polynomial-time algorithms to approximate a minimum cocoloring on graphs, partially ordered sets and sequences. In particular, we obtain an efficient algorithm to approximate within a factor of \\(1.71\\) a minimum partition of a partially ordered set into chains and antichains, and a minimum partition of a sequence into increasing and decreasing subsequences.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853153$9834285F-1EB8-4910-9E24-E0EF30667A89","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853153$74F41A03-C1C7-4C05-A5AC-C1B90CA8E79A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853153$E4A96214-DC27-48DA-9B7E-AF362F36571B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ac837210b320c07d90b7975d079af2b2d513d3bf","datavalue":{"value":"1856489","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853153$D5B8C4A0-D7AC-4947-8277-25170C1AE5F4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbff35acdd31439d13dd3892bdda5725c18fc300","datavalue":{"value":"Approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853153$126DA5B7-1032-41F8-BB18-A61A0E335F7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4cb595c31c3aa9f45effd9d2cfa751cd06093be","datavalue":{"value":"Graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853153$CA0CA7A4-572E-4871-83D0-8D9B40F4F84A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f00a780bf89b136c3716dce59ea7779b7fd54b3","datavalue":{"value":"Partially ordered sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853153$BA022C9C-BFA1-4359-A824-BFF4901DFAF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41e50d9a21aa5db2356f9471896abaa277cac60d","datavalue":{"value":"Sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853153$AD257F77-27C1-44D2-B47D-3E41E58B52C1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"57e98d9c9076a2a5f553959b440bd4c05a2986fb","datavalue":{"value":"Q56428494","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853153$37C6D059-3E06-4F92-A691-A8D9803A101A","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":"Q1853153$A2119BA6-F614-4963-AD33-151F6AC1BEDB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc4ccf960029167669317eac77ca96c068676f5","datavalue":{"value":{"entity-type":"item","numeric-id":4351317,"id":"Q4351317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$6E95374B-29E9-4AC6-B66B-1DCBD2841611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"168aa84d4d8a2e9301ac43dc2592dcbade60f1c5","datavalue":{"value":{"entity-type":"item","numeric-id":4724636,"id":"Q4724636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$7DEB9C8E-D3EF-47AA-8EB5-819389F5D21D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"282d88b529308441c287f6c692de7afeae122bdc","datavalue":{"value":{"entity-type":"item","numeric-id":4243764,"id":"Q4243764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$844BF97C-5935-4C04-A873-32D51890EA83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"951152e2b84bbaba3cb745c04328e875ca0fdf27","datavalue":{"value":{"entity-type":"item","numeric-id":3832592,"id":"Q3832592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$30DD93AA-353F-4B42-8057-B87163023E73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd7bfc1f19052d02bdfe94ca5fef0563472563dd","datavalue":{"value":{"entity-type":"item","numeric-id":3139768,"id":"Q3139768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$3ACAA800-91C1-4CBB-A02A-4ACD2B4C04F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c631808fbf833c73fc0a78295d8c2cb38d4d9852","datavalue":{"value":{"entity-type":"item","numeric-id":3984467,"id":"Q3984467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$D50B0690-5C08-4632-AA6C-35FEF1CC5432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06cdbcb5383e14fdbe200c9f1d757c7ab522ba3f","datavalue":{"value":{"entity-type":"item","numeric-id":2640609,"id":"Q2640609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$791CCBBD-6BD5-4786-B2D5-BFB04C79F5B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14079f9b550ba1f661483da97df5df73cda997ac","datavalue":{"value":{"entity-type":"item","numeric-id":1144050,"id":"Q1144050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$EF454143-3836-4F10-9113-36771A21D58C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f41fa9ac2d3cb9750dbfda0b76b6559f82f9ac9","datavalue":{"value":{"entity-type":"item","numeric-id":1315460,"id":"Q1315460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$B0FFFA8A-E6B2-4E9E-9559-195EB068E8EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a940fb332b14d2ba62f7a4ab977a0ec13ed35cf8","datavalue":{"value":{"entity-type":"item","numeric-id":1121278,"id":"Q1121278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$C4628CAF-D7BA-48B6-9E2C-D3ABFE31B77D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$2EFAB22B-1A68-4325-AC63-CA47572E36AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74f022c5d6b08439aa878e2ed1f5966d14821894","datavalue":{"value":{"entity-type":"item","numeric-id":1224110,"id":"Q1224110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$BD61965A-ED40-4686-99A4-090772CB8FF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3540803e6c2941a79b658c1ad46488049de9a54a","datavalue":{"value":{"entity-type":"item","numeric-id":5966939,"id":"Q5966939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$778B4790-1C0A-457C-8081-32F12E2D8A0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16b4d29c0ba31b1bc8e06218af428a76fc8ce67","datavalue":{"value":{"entity-type":"item","numeric-id":1210712,"id":"Q1210712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$178DC6FC-F0B1-4204-B749-90F48B023032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$9DD9F902-98C0-452A-A04C-DFE8FA65C900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"331fd72e5d537a569b6a661259ebaca4c6bb394d","datavalue":{"value":{"entity-type":"item","numeric-id":4175304,"id":"Q4175304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$8057FBC0-42EB-443D-86E5-B272C71D2E4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db3468346fcce29d2fe703e3816d1c0ffadbf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1224109,"id":"Q1224109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$BBA169A5-522E-4DF4-89AF-B16EDF1F3633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e52440870859d0d8f40f493cc0c996fef77b351","datavalue":{"value":{"entity-type":"item","numeric-id":4184857,"id":"Q4184857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$7F8A0927-076D-44EC-A09C-409C1BDF16A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74812f4ed9ebba0d1b8d4a1c69da6a61f9a0bb72","datavalue":{"value":{"entity-type":"item","numeric-id":3681937,"id":"Q3681937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853153$F7CADCFC-D5D0-42DA-8817-B3E67850EC44","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"abc5c3767afd7980f48462ebe209b6df500fd77c","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(02)00288-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853153$48367953-DA0B-4724-AEEB-CB9BDA2286C3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a53993224fdf2826b0670525dd058b76c92b8ac5","datavalue":{"value":"W1984312288","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853153$6E1D26A4-5213-47E8-9E21-2ABD11A5F460","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"60bda2a02215a19caf81835d450d3e1537653856","datavalue":{"value":"journals/ipl/FominKN02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853153$95D0F42B-299B-45FB-B51D-6BDFF2EFDE0B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0baa89e7ee10f852f9764f53232149a4bdbc3ac4","datavalue":{"value":{"entity-type":"item","numeric-id":4782702,"id":"Q4782702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81dc1f5392f9cd8d203d6905171f283e8d403b18","datavalue":{"value":{"amount":"+0.9591450691223145","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":"Q1853153$AC3657AC-C8F8-4321-95DA-E1F75E0E83EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df40d633d0ba329c0cd451a1fa74ad609494f0f5","datavalue":{"value":{"entity-type":"item","numeric-id":4943070,"id":"Q4943070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81dc1f5392f9cd8d203d6905171f283e8d403b18","datavalue":{"value":{"amount":"+0.9591450691223145","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":"Q1853153$C2115DAF-725C-4F45-8972-0C5822504D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d852281be976c63a22663537a6a29b925b01e70e","datavalue":{"value":{"entity-type":"item","numeric-id":5301394,"id":"Q5301394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"233ec81cd49bcdf5bee5fa620d44d9325c8bd675","datavalue":{"value":{"amount":"+0.8211830258369446","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":"Q1853153$B3C8A6C7-DB7A-4E50-9F74-3B8C2CBC9024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ee18b39c68c26b2f2d625134e9dec18767e2783","datavalue":{"value":{"entity-type":"item","numeric-id":2568333,"id":"Q2568333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e0697870692b38fb72386efb5e783fc1c7268f9","datavalue":{"value":{"amount":"+0.8113416433334351","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":"Q1853153$2E0BF4DB-BC4A-4C3C-AE02-7E11D904BACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9456f0b6d5fdc364e90e5031c6fb75410fd8015c","datavalue":{"value":{"entity-type":"item","numeric-id":1315460,"id":"Q1315460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb1be5cffab79f7013b7223e116ec1006b4dd5ea","datavalue":{"value":{"amount":"+0.8028786182403564","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":"Q1853153$7829395D-B48D-4BF9-B95E-2DAC395E80AB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximating minimum cocolorings.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximating_minimum_cocolorings."}}}}}