{"entities":{"Q762183":{"pageid":764032,"ns":120,"title":"Item:Q762183","lastrevid":64184727,"modified":"2026-04-11T18:11:41Z","type":"item","id":"Q762183","labels":{"en":{"language":"en","value":"Minimizing setups in ordered sets of fixed width"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3887750"}},"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":"Q762183$C8483F58-C6CA-4D45-ADC2-DC2C4CB65AE9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0298c08ceee956e596b51d9419def757a14cf5e9","datavalue":{"value":{"text":"Minimizing setups in ordered sets of fixed width","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q762183$E23A1065-B455-41B0-8D25-AFC6D8ECA46B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a9babc595400a11facc82eabf626db82cc2a6fe9","datavalue":{"value":"0557.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q762183$93D6F80F-920A-47D5-A4BF-075E7B01EE28","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3bc739a112686eebb0ac3f08a29d9e76b7ca2542","datavalue":{"value":"10.1007/BF00383598","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q762183$C2FC7455-5200-4A76-90AD-E9829E7A5E85","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff87f54c8625b230f23e0ff9df421fd57253f22c","datavalue":{"value":{"entity-type":"item","numeric-id":582214,"id":"Q582214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$0F0DD8CB-0C5A-4477-917C-AC949A75622B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbbdc3381c094a1abe2cf60ed445a4984b25837b","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$0E698F32-075D-41A4-AD5C-7324E7BBDD53","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$2C5429C9-2C80-4D6F-954B-B4E46617DCC6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q762183$2C077942-9423-40DD-891F-116A80FD5E63","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ec303d0f5743d060ce5a5aab578806fe0bd7210e","datavalue":{"value":"If P is a poset then the width is the minimum number of chains which cover all elements of the ordered set. If L is a linear extension of P, then s(P,L) is the number of pairs \\((x_ i,x_{i+1})\\) which are not related in P, but are consecutive in L. The setup number s(P) is the minimum of the numbers s(P,L). In this concise paper the authors provide an elegant polynomial time algorithm for computing the setup number of an ordered set with fixed width (Dilworth number). This generalizes work by Chein and Habib and falls in a class of different algorithms for different classes of posets, several discussed by the same authors elsewhere.","type":"string"},"datatype":"string"},"type":"statement","id":"Q762183$5B9F3FDF-7777-487F-A7F4-22F2FB1ABB2E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q762183$0BCB6DBC-F421-41F3-BF72-085821D99A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q762183$BF50ED68-A78D-4ED0-B7C6-CFF098859E2A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"494b991d4cefbf7d538e0cef26ef7fdd6db598f2","datavalue":{"value":"3887750","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q762183$D6D729FE-C046-42EA-B077-F5F0F912DE37","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccdf98bea6de3dcf3a7edd1fca9d3b62359e75d8","datavalue":{"value":"width","type":"string"},"datatype":"string"},"type":"statement","id":"Q762183$B74403A2-DFF9-4DA8-B0D8-55C57FE21F3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ad5599d0b8005742d4eb354b6906a61e9640688","datavalue":{"value":"chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q762183$99307FAE-3381-4DA0-9397-57F583D2388C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"311b860a0597dd249b584149fd2ab2e7e5bfa5ec","datavalue":{"value":"linear extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q762183$ADCC6712-9A72-490F-9D9D-4118F880FB31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e296e3d542f5b74db7b5ce88a2efe4d392542223","datavalue":{"value":"setup number","type":"string"},"datatype":"string"},"type":"statement","id":"Q762183$00528C4A-DD6C-4C2B-AA14-CBE2EED17422","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q762183$14667419-1280-4EE3-B327-A92F168E9FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f99266d14fac1b5b9e7ee01bb7b35c4d18bf8fa9","datavalue":{"value":"Dilworth number","type":"string"},"datatype":"string"},"type":"statement","id":"Q762183$DD9BB690-4AB2-4F3B-B3EA-039FB5C6A75E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55ed4e02075ed4e4b1b42997cccad7cede0fb5bc","datavalue":{"value":"posets","type":"string"},"datatype":"string"},"type":"statement","id":"Q762183$EB0448AC-CC8B-4A83-8403-8CB9B9FE00CB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b626688718ca3d61fce8479b1c17fa40d92d8dda","datavalue":{"value":{"entity-type":"item","numeric-id":233347,"id":"Q233347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$9257BC25-2034-48B2-9468-DC57F45B499D","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":"Q762183$B3A60B6B-F5A9-4487-951B-2A35E6349CF2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"89d18f16e8c7f370dfcb7fb9d88b670fd5f0dc27","datavalue":{"value":{"entity-type":"item","numeric-id":791537,"id":"Q791537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$985F9934-E444-4373-ACD5-450BB88BDB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8553feea678bc899d05f5a147512f8d0b1b46f91","datavalue":{"value":{"entity-type":"item","numeric-id":3960747,"id":"Q3960747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$E714204D-65CF-4DF0-B26E-1C74F1A69B0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03c5849a9bcf15140f1ba37c44be594fd69e35a7","datavalue":{"value":{"entity-type":"item","numeric-id":794156,"id":"Q794156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$009551D6-AA6B-44C5-B8F0-31A669138863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eab28dee024bf7d24f20a12a054e9f818b17b7b5","datavalue":{"value":{"entity-type":"item","numeric-id":4147824,"id":"Q4147824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$1A6C10BC-DBDA-46C0-B27B-13F2D37DC610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0eaad8cb814fca5f62e5714c899a7fcd111a86ef","datavalue":{"value":{"entity-type":"item","numeric-id":3698661,"id":"Q3698661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$AB765D8B-013B-4759-A42C-26F2E7F3999E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad905585949c2d77be6b8ef7e888f59707dd06c4","datavalue":{"value":{"entity-type":"item","numeric-id":1057887,"id":"Q1057887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$581E0123-80F0-41FB-A7D5-F2C10886CBE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d5b3cac9d7fa9b0244c1deee93551fd12a68a92","datavalue":{"value":{"entity-type":"item","numeric-id":3676161,"id":"Q3676161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q762183$A5EC9871-C2B4-4C35-AFF9-04D57D08B98D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6756b41779efab71b7eddd8cc2868a09948b038","datavalue":{"value":{"entity-type":"item","numeric-id":2222933,"id":"Q2222933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"982c834788c6ba17fec4d7d0fea4507f982e40c1","datavalue":{"value":{"amount":"+0.8604716","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":"Q762183$B10DB39A-E028-4697-B37A-B088479CF110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d22302f868340b4b010af0b1baa20884710e345e","datavalue":{"value":{"entity-type":"item","numeric-id":5384087,"id":"Q5384087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89fae65f37488efa0b5ca428868c0032ab9f777a","datavalue":{"value":{"amount":"+0.85679835","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":"Q762183$512EC532-7DDB-48EB-851B-07FAA2948CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d1970a1c9b0ed434309d8b14c6c4d23f32dee5b","datavalue":{"value":{"entity-type":"item","numeric-id":1133558,"id":"Q1133558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"262b6a1401ed8344ed623eaa071a89dc198bb556","datavalue":{"value":{"amount":"+0.85410416","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":"Q762183$E296E413-559F-49CD-94DA-1E5A0FEBD1D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1eb5481349c4c56ef87b6c00f5677fe18c4c703e","datavalue":{"value":{"entity-type":"item","numeric-id":1177708,"id":"Q1177708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36c20d6c2757c69af54dc48b7010d3cb782329c0","datavalue":{"value":{"amount":"+0.8483567","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":"Q762183$34E47D2E-AAF9-48E9-9ABA-73DB9B42C4E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b624680d8fc574517d233b9fe063f2924eed5ebf","datavalue":{"value":{"entity-type":"item","numeric-id":1114719,"id":"Q1114719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc8d78e3e881422f1137f3b7df113029c18b8722","datavalue":{"value":{"amount":"+0.8461783","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":"Q762183$85E45433-3B55-4511-A0FD-431C96396761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc2430b3e869010c4b6cbd70af6cff69b4de99e1","datavalue":{"value":{"entity-type":"item","numeric-id":4017185,"id":"Q4017185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc71d8c92dedcd074dea7b041bec5233f60b628e","datavalue":{"value":{"amount":"+0.84535587","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":"Q762183$EB1609F2-3EBD-4456-94C8-20BCF413E2BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29fdf63cb8b09e550da5e3f55dd99ca0223975b9","datavalue":{"value":{"entity-type":"item","numeric-id":2413151,"id":"Q2413151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17c2d277e8172694068c11b320248f1a5f1a03fa","datavalue":{"value":{"amount":"+0.8427245","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":"Q762183$B772307D-FB53-42EF-B21B-76405188BD2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"808130a30de3b52baf7e17973cae5cd11fb79e69","datavalue":{"value":{"entity-type":"item","numeric-id":2899100,"id":"Q2899100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5180030dc282caf0dc1d4439484a10ecd36cddc1","datavalue":{"value":{"amount":"+0.8404019","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":"Q762183$368E57D9-D2F2-4B07-A130-C476C9A46FF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3be8d4b6df22724c73552c2950964a5edd2b6cf","datavalue":{"value":{"entity-type":"item","numeric-id":4796669,"id":"Q4796669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5201fd308635b22d81031e4ce7fd5bd4fb96548","datavalue":{"value":{"amount":"+0.8394729","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":"Q762183$BF1E4563-4417-47E4-9C2D-0D0FB5D29669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9947b6eaa43674cb322831e41ca3b8528e0f3dcc","datavalue":{"value":{"entity-type":"item","numeric-id":4518696,"id":"Q4518696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"406eef0ff20b72ba3e5d59ab37608b43ee4e7576","datavalue":{"value":{"amount":"+0.8392318","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":"Q762183$597DE8B0-F188-4A6F-84A5-45836B85438F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimizing setups in ordered sets of fixed width","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimizing_setups_in_ordered_sets_of_fixed_width"}}}}}