{"entities":{"Q1178732":{"pageid":1189481,"ns":120,"title":"Item:Q1178732","lastrevid":66512118,"modified":"2026-04-12T10:34:40Z","type":"item","id":"Q1178732","labels":{"en":{"language":"en","value":"Color constrained combinatorial optimization problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 22309"}},"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":"Q1178732$2463A280-F004-4577-BFA4-9FBEA10CCEB5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d33e09126cd0cf9cb9dc6da660d3a27b93b1e3ed","datavalue":{"value":{"text":"Color constrained combinatorial optimization problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1178732$E55B6992-0A5D-48AD-8F15-D1E834A62127","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"83b12c16e6f074a14eb85db15c4a81908ee53760","datavalue":{"value":"0745.90061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178732$965920FC-1988-45D7-952E-6CA5500FA32F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"152ea8615b955ec29508a727fc848db55beb8f11","datavalue":{"value":"10.1016/0167-6377(91)90061-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178732$5C671869-EECC-45E5-8206-29F7C68EAAD6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"958e6776d72e0cd3a765c49e10c9b7cac6fe0984","datavalue":{"value":{"entity-type":"item","numeric-id":240162,"id":"Q240162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$6A086216-751C-4BA6-8A8C-909CCA627DA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e50be6e020f540bbd257789357e2fcbd9ed3a74e","datavalue":{"value":{"entity-type":"item","numeric-id":166234,"id":"Q166234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$5E356B5F-A50E-468F-84B0-5C5CFE4A480A","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":"Q1178732$D5B8A525-A609-4D59-B9A3-88EFC96AAE7F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1178732$495E56BE-FE2A-4A5D-B503-FC5FA1B912BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7635ee28d18f1a4ba4a8b816336a60f58f594cc2","datavalue":{"value":"Let \\(E\\) be a finite set and let \\(c: E\\to Z_ +\\) be a non-negative integer cost function. Given subsets \\(E_ 1,\\dots,E_ K\\subseteq E\\) (colors) and \\(\\ell_ 1,\\dots,\\ell_ K\\in Z\\), find \\(\\min\\sum_{e\\in S}c(e)\\) satisfying \\(S\\in{\\mathcal S}\\), \\(| S\\cap E_ k|=\\ell_ k\\), \\(| S\\cap\\overline{E}_ k|=R-\\ell_ k\\), \\(k=1,\\dots,K\\), where \\(S\\subseteq E\\), \\(\\mathcal S\\) is the set of feasible solutions, \\(\\overline {E}_ k=E\\backslash E_ k\\) and \\(R=\\max\\{| S|:\\;S\\subseteq E,\\;S\\in{\\mathcal S}\\}\\). The authors show how to reduce this problem to a parametric problem with paiwise disjoint colors and derive as special cases polynomial algorithms for one instance of a 3-matroid intersection problem and colored bipartite matching problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178732$301DB41F-891F-4DC7-AE95-F11DE7605698","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178732$37C0D4F2-0D66-46CE-90BA-AA42760DAF21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178732$94B474A7-D501-40E8-9313-AB7AB98682CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178732$A3198421-6116-4DD4-BDA1-23186885EE89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178732$833FE21D-FC4F-4B35-986C-4A437330418F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5287e745ddf2b296067ebbea7cd39e4b944f6355","datavalue":{"value":"22309","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178732$8E300FE5-D7C1-4402-8524-8E44AD145CE3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4435355c9c34b5a1ebc8d726c175ff4ccf7cb9c3","datavalue":{"value":"color constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178732$9116463F-8046-4FA0-AE54-DB261B7D3E07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178732$B99D3F70-CAE8-4425-985D-DDBAEBE1B564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afb9d181e8a78e6ff2d10ecec84bb9bf8a556d13","datavalue":{"value":"3-matroid intersection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178732$BD4A83B1-1A32-49E4-BFC3-C2E06B902C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a0c1775b68a254ccbe23168b1de8db2c89421b7","datavalue":{"value":"colored bipartite matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178732$4885E87B-D054-4C3B-8AE0-8E79B2734983","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2b972ef175b4299fdbfc53bb71881ff0c6d5f85c","datavalue":{"value":{"entity-type":"item","numeric-id":587047,"id":"Q587047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$598D0F07-4F10-46B5-8B11-0967CE7E407C","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":"Q1178732$729544AF-40F7-42CA-9A2F-098D032F9F47","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$7944C464-A635-4AC6-A4C2-E8812D80D57C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3d25a1a5e53297c46a66ca1d4755989c397bf3e","datavalue":{"value":{"entity-type":"item","numeric-id":3770280,"id":"Q3770280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$FE2711B6-BE33-4119-AC30-D2BFE0E7052D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f98d6c76861b2236c25cc43f18dcd8c521928b27","datavalue":{"value":{"entity-type":"item","numeric-id":1116893,"id":"Q1116893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$A8EB7D1C-BAB8-4312-B355-06BC00B42D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43798c19208231d39c6c4f059a0476d674a2816f","datavalue":{"value":{"entity-type":"item","numeric-id":4149476,"id":"Q4149476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$F38D7CA0-DF5F-4CF0-BA03-B247AD91A437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9beef10f14c1534c9b646b394bb6806fa6bcf5a6","datavalue":{"value":{"entity-type":"item","numeric-id":3335803,"id":"Q3335803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$FE689132-6FE5-45F8-9735-9AAF6859E5A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1a7e29801581e9e5a5187db25cd480c84107d91","datavalue":{"value":{"entity-type":"item","numeric-id":793743,"id":"Q793743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$38F5480C-6B48-4C17-9CF5-053AB463231D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5eee13469c8a40bd22b5fe6b3a3573ce9cdbaed","datavalue":{"value":{"entity-type":"item","numeric-id":3470256,"id":"Q3470256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$0549FF79-2694-4066-9620-68CC1D983193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c79ba1a23783edbacafc84d742f2fe6e993929eb","datavalue":{"value":{"entity-type":"item","numeric-id":1825757,"id":"Q1825757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$6E645506-FD8E-46EF-BA25-9B5AAC82F42A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18896b12fcfc75b1384ddbb4d217a7db3a02e745","datavalue":{"value":{"entity-type":"item","numeric-id":1079110,"id":"Q1079110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178732$FC2AD9D6-A06C-480B-9311-997985F3D1A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9e2bb6b9859cf0873596899ab63533f4f9f2d3da","datavalue":{"value":"https://doi.org/10.1016/0167-6377(91)90061-s","type":"string"},"datatype":"url"},"type":"statement","id":"Q1178732$ED717096-C4FB-44A6-B1A2-1FF7820F1579","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"19adbdd6991eb80f33ee31a13fffe36d820813b5","datavalue":{"value":"W2060093257","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178732$FF3A95D8-4497-4C2E-89B6-700C8FABF51F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"602284fcd76f40fe042bf377880f6fe0147f2855","datavalue":{"value":{"entity-type":"item","numeric-id":1825757,"id":"Q1825757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0873f0822ee75ace01672880f5e1bfcea7d9af55","datavalue":{"value":{"amount":"+0.7963319420814514","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":"Q1178732$695CD927-D23B-48EF-A002-E36E506386C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"306282e58bbdfc0c70accbc5a4c6f35e6798eda9","datavalue":{"value":{"entity-type":"item","numeric-id":1902899,"id":"Q1902899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9175a16a29bd80158cb799272e30939a393ca78","datavalue":{"value":{"amount":"+0.7922171950340271","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":"Q1178732$CEFE223B-5A1B-44AA-BDF4-750A09398680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e61ec7d4ece6914eaa7e4b7017b769b27da7f4b7","datavalue":{"value":{"entity-type":"item","numeric-id":3335803,"id":"Q3335803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d24eacbb172008cdce557bc749ef27f1e3c16ff5","datavalue":{"value":{"amount":"+0.7662807106971741","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":"Q1178732$2346E113-0272-404D-8CCA-2E7F9B401644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"919a7ed610b99cdc861a8de44c8c58c393dd5c58","datavalue":{"value":{"entity-type":"item","numeric-id":2835676,"id":"Q2835676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20fb56d6552f22050d84f90e2c06e2bf734a9573","datavalue":{"value":{"amount":"+0.7652254104614258","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":"Q1178732$A3A7C172-8CF3-496E-A140-7A045A7A4C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d049b2867fc19c693dbf3c93c07edd6cb2817ab","datavalue":{"value":{"entity-type":"item","numeric-id":3823151,"id":"Q3823151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb76ff118b3de6ba8891d323e7451d8db35d7ffd","datavalue":{"value":{"amount":"+0.7597589492797852","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":"Q1178732$47240C64-2234-417A-B93A-78A59920D515","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Color constrained combinatorial optimization problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Color_constrained_combinatorial_optimization_problems"}}}}}