{"entities":{"Q1095668":{"pageid":1106420,"ns":120,"title":"Item:Q1095668","lastrevid":69826986,"modified":"2026-04-13T10:36:49Z","type":"item","id":"Q1095668","labels":{"en":{"language":"en","value":"An O(m n) algorithm for regular set-covering problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4028924"}},"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":"Q1095668$56ECF066-F313-4776-8B54-B9BA6AE39D71","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f0a586bfbc2d193133b30a533b9cb4c2540a487d","datavalue":{"value":{"text":"An O(m n) algorithm for regular set-covering problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095668$9417B755-EC3F-467F-B879-7DCBFE91D3D4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d7be57eeaf2c8a026b04e261d4263f5ea0e8f29d","datavalue":{"value":"0632.68068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095668$9515C32A-9338-4072-9ECE-F103B1028C24","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e8071fa4d61c245dfa09ea7cba37666b7ddfc520","datavalue":{"value":"10.1016/0304-3975(87)90131-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095668$A30562AE-5210-46D4-B8B0-10A75720488B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd94e4e7f27f948a7315c2ac01ba439ef6354378","datavalue":{"value":{"entity-type":"item","numeric-id":235657,"id":"Q235657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$E3EC8E66-692D-4C5C-8C4C-D67E985794A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3de34c40bbd436145163ee502934245d6246cef6","datavalue":{"value":{"entity-type":"item","numeric-id":173870,"id":"Q173870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$253B497F-ACCE-4C8B-9234-2ABE9348622A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$6A4BACF9-62D1-45C7-AF3A-5FE9DF0A9056","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1095668$F0D0E0B2-DC75-411B-BA78-2894485D060C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ddb9c54edddd70d3330ebe5b598509a8f3aa6d0","datavalue":{"value":"A new algorithm for solving the optimal set-covering problem is established for the particular case of regular sets [\\textit{P. L. Hammer}, \\textit{U. N. Peled} and \\textit{M. A. Pollatschek}, IEEE Trans. Comput. C-28, 238-243 (1979; Zbl 0394.94036)]. It is proved that the complexity of this algorithm is O(m n), where m is the number of elements in the given collection of subsets of the set \\(\\{x_ 1,x_ 2,...,x_ n\\}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095668$C24C3DC9-E855-4382-A023-324946DF5499","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095668$4DB1AA98-55D5-410C-8EDB-72B6E6895E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095668$C819D591-FBA4-48DE-9576-92E370090315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095668$1DFF67D4-9973-4891-A0ED-830A242FE2C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68268172085cfff95462799d35e58660b52cba5f","datavalue":{"value":"4028924","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095668$5A550F2B-A694-41B5-9751-4BBD737C5B3A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f947314c99417362d0c49300ef304830a6b3ad9","datavalue":{"value":"regular switching functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095668$2634AEC9-5B52-4C6A-889D-80CC70228164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10bfd620238f21a6cf204a2f84c82168a6d83367","datavalue":{"value":"threshold synthesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095668$A8A3DDA7-904C-42DF-941C-3CCC121141B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfef22503bd86e9b87a17a964db3875c474af9a0","datavalue":{"value":"clutters","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095668$C71450D5-A9B7-4F0E-B3BF-E7D66753653C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f434d7114c7bb100b3a854d1fa4c5684ed2ba21","datavalue":{"value":"polynomial algorithms. optimal set-covering problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095668$1D51749D-E84C-43FE-A02B-6DDE3EF18301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d6f538b08e69057661b54b3efc02988b26d9938","datavalue":{"value":"regular sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095668$85E200CB-34B0-4724-935F-7E4527A5A917","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":"Q1095668$7871DBEA-8395-4692-9714-AD98E61E398B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ff2c29f5e30f261c0b97896ebfd558493e1f7c06","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90131-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095668$4D5A71D4-2A99-4EF3-940C-E83C06CB0D60","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6c1f5a645327695c0be1ceeee035d54bf0b8ba3c","datavalue":{"value":"W2051364416","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095668$6632280D-FCDF-42CF-8FFA-F3192921F335","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$E837C953-9351-492F-8473-FE27796E026B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ff5815c38d237a74f6b5a82910f7cd714253562","datavalue":{"value":{"entity-type":"item","numeric-id":3834089,"id":"Q3834089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$4739F3A8-C68A-4CE9-8051-5D3C316456C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d480e9df94b7466b2d1a2ed0fa6cca9dbe2d90ab","datavalue":{"value":{"entity-type":"item","numeric-id":1084376,"id":"Q1084376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$87EB41D3-1F9E-453E-93CF-10F57BA7A154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5395d0bcd819be45c30e27db1452a43996bbd557","datavalue":{"value":{"entity-type":"item","numeric-id":4060733,"id":"Q4060733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$1665D1C0-3870-40CD-AC19-A52862DEB83E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d8501cee493f055738f00aa7c9c9ea46a233211","datavalue":{"value":{"entity-type":"item","numeric-id":4177485,"id":"Q4177485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$55935855-1175-430F-9CE7-D3C9927B77C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"321025a28122a24e3295ff0bfb23f7e670c5268d","datavalue":{"value":{"entity-type":"item","numeric-id":3758559,"id":"Q3758559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$C9DEB7AA-C89F-4596-ADDA-D20F7CB71E4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d6b53860e99ce6968cd8d98dd7f7f3f11538c56","datavalue":{"value":{"entity-type":"item","numeric-id":1089348,"id":"Q1089348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$B4647F7B-8A15-49DF-B9F4-24F2ABDBD373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ba81c30cda24c3d605c0679939d82fa6643c181","datavalue":{"value":{"entity-type":"item","numeric-id":5822054,"id":"Q5822054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$DAE08546-F9F9-438B-88E8-AB66B0E7F9C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"119d14273a5178c9fdb0109f5da7d88db66c689c","datavalue":{"value":{"entity-type":"item","numeric-id":1245970,"id":"Q1245970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095668$54F80E30-F377-4599-BD5A-7ABB4E09B062","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e0a852a3412340e7af9be1d9daefb6cc927d935","datavalue":{"value":{"entity-type":"item","numeric-id":1823139,"id":"Q1823139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ef9533fdaa25bcc7fe76e729a10be698451742f","datavalue":{"value":{"amount":"+0.8314812183380127","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":"Q1095668$EE68805C-EB23-474B-A3C7-F264E8B7571F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b02ac15f0bf09b145168da29e90e3ec63f5e80e","datavalue":{"value":{"entity-type":"item","numeric-id":3690585,"id":"Q3690585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"452bb567f180c90a8025667a71e02a8f8c128fde","datavalue":{"value":{"amount":"+0.8028168082237244","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":"Q1095668$289F5D15-7363-4629-8B51-C4033500A2B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9519eaaef3f0ab87638d3f36f1b69fb78c911285","datavalue":{"value":{"entity-type":"item","numeric-id":1089348,"id":"Q1089348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce5ea57be4480811159e99bf74059d4f340a0b2c","datavalue":{"value":{"amount":"+0.8019611835479736","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":"Q1095668$D4251FBB-F077-4266-893C-7077B116D6AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"040b6f38178066b6c39bd5dd0026d44cc08c76b5","datavalue":{"value":{"entity-type":"item","numeric-id":2713942,"id":"Q2713942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2226c0cadb73df6236c7b0c1d93ae1e508de6101","datavalue":{"value":{"amount":"+0.7994682192802429","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":"Q1095668$A00F6755-51F2-4CEE-B32A-12CB3F3BBC4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"caf170789a58b17db68634bb64b1ffed3bfd255f","datavalue":{"value":{"entity-type":"item","numeric-id":4817473,"id":"Q4817473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8066e58296f0a13f39d4c46d84addd599f471889","datavalue":{"value":{"amount":"+0.7931704521179199","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":"Q1095668$CBA9CAB6-D44F-4E54-AF7A-E265F8AE18BB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An O(m n) algorithm for regular set-covering problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_O(m_n)_algorithm_for_regular_set-covering_problems"}}}}}