{"entities":{"Q1106865":{"pageid":1117614,"ns":120,"title":"Item:Q1106865","lastrevid":49194583,"modified":"2026-01-06T18:06:17Z","type":"item","id":"Q1106865","labels":{"en":{"language":"en","value":"Computing the bump number with techniques from two-processor scheduling"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4063159"}},"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":"Q1106865$49F1D851-0513-451D-885B-A6898E126EA1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"065f2ef5340d1b915cd60b1862e0268c6fb993c1","datavalue":{"value":{"text":"Computing the bump number with techniques from two-processor scheduling","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106865$F549F13E-4A87-4CBC-BBB3-DF9942EC33DA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d903f87deaabc74194b67f742febebfe2cfb6dbf","datavalue":{"value":"0652.06003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106865$9101924F-3A1E-4E8C-A83D-7C3C53B33D6C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b99ca797f4f69e2b87e01c4e0083743ae28e609f","datavalue":{"value":"10.1007/BF00337618","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106865$C29F2F84-D456-4E50-87FC-B2F1A0C886BC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"26746dbc33f3758ff0c811c5b77df5443ce35694","datavalue":{"value":{"entity-type":"item","numeric-id":672747,"id":"Q672747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$B4832042-9A7F-4E02-9C2C-8CDE839A09A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"212f3659b1e8af11d124555eab180b99ae2c6fac","datavalue":{"value":{"entity-type":"item","numeric-id":1106864,"id":"Q1106864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$5072FDC7-7BA2-4591-946F-E00DCAADDBE0","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":"Q1106865$AF0A0A27-AF76-4986-AB23-BAB1C013574E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1106865$333A19F5-84F1-4305-B18C-3BE4B8FEB71A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9dba2edfafac06069d5907a28befcc291f115896","datavalue":{"value":"Let (X,\\(\\prec)\\) be a partially ordered set. A linear extension \\(x_ 1,x_ 2,..\\). has a bump whenever \\(x_ i\\prec x_{i+1}\\), and it has a jump whenever \\(x_ i\\) and \\(x_{i+1}\\) are incomparable. The problem of finding a linear extension that minimizes the number of jumps has been studied extensively; \\textit{W. R. Pulleyblank} [On minimizing setups in precedence constrained scheduling (to appear)] shows that it is NP- complete in the general case. \\textit{P. C. Fishburn} and \\textit{W. V. Gehrlein} [Order 3, 3-14 (1986; Zbl 0595.06004)] raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear- time algorithm for the two-processor scheduling problem solves the bump number problem. The authors of the paper reviewed above (see Zbl 0652.06002) have independently discovered a different polynomial-time algorithm to solve the bump number problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106865$4B690828-4F0E-4E3E-B450-D71965C6125E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106865$4A1FB5E2-1F46-4BBD-85E4-E12DC38FDAF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106865$68E6487F-1C61-45A9-B6EE-428EF898441A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106865$FE020BB9-A32D-4300-B7A1-B6A9D3A1371B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106865$29FA889E-DC6F-4910-BABA-9D2132A48B18","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c99c9a4420604e34cd58554af3bea70244f924b7","datavalue":{"value":"4063159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106865$E705F988-6CCB-4DFE-BAC9-07C7736E0D60","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"311b860a0597dd249b584149fd2ab2e7e5bfa5ec","datavalue":{"value":"linear extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106865$BEBCC729-513E-4E59-B493-A2CC8E57ABD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45ce782da195090588818a066a1f104d5fd148cf","datavalue":{"value":"bump number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106865$BCFB9958-77FE-436A-8B17-338F92B6DAC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a127ca9dee32dae755d85924d37aa755b82da29a","datavalue":{"value":"scheduling unit-time tasks with a precedence partial order on two identical processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106865$0EFB302F-F894-404F-AB99-21782607C6EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106865$23CA4541-3FCD-4D5D-96B6-E6902C9B6A93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38babb0d36bcb8e756a92965ddefab42ab4d75c6","datavalue":{"value":"two-processor scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106865$3F7B40B6-0C71-401F-BCCA-60AF16FB18F3","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":"Q1106865$171F2F46-BF74-45BF-9002-D2F01188479F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9398e17eeb53f4734fe395088f4dea16c8f37eb3","datavalue":{"value":{"entity-type":"item","numeric-id":3868759,"id":"Q3868759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$A96D7D71-F9D4-43D6-8E19-78C7921BE05A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6d199017df4d3146f497fbc8db45c8d467a421d","datavalue":{"value":{"entity-type":"item","numeric-id":2556224,"id":"Q2556224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$7B07EEBF-D35F-4C08-AD66-E02DC43749DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b944833fa97de961f22b519a3ec130cc1d9cba93","datavalue":{"value":{"entity-type":"item","numeric-id":1077441,"id":"Q1077441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$578DF014-5603-4B1A-9A88-F535D09545F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af28b9a9a2726877574bce10970dc72b6773750","datavalue":{"value":{"entity-type":"item","numeric-id":5605625,"id":"Q5605625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$CADD99BB-4975-4AA7-A052-8A642B41E12A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80d6755d506c6ab886e46304ba47fdcd2c104ea6","datavalue":{"value":{"entity-type":"item","numeric-id":3945581,"id":"Q3945581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$D6EA4CE5-8940-47C6-BE35-3D415CE7419B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17b46f23e1d95210ec444c78dd7a8edd18f2e48d","datavalue":{"value":{"entity-type":"item","numeric-id":1062461,"id":"Q1062461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$FF261E9C-1795-4B14-A8F7-31D8E6C9451C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"209a53d1b241380cdafb79969e0e9def1f032b49","datavalue":{"value":{"entity-type":"item","numeric-id":1106863,"id":"Q1106863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$E1774E1D-6C87-46A2-96E2-F15E1070E845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"720cb0112745e0fc4d414a8652264da0bad7fa31","datavalue":{"value":{"entity-type":"item","numeric-id":3731028,"id":"Q3731028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$7B546E4B-2221-45E2-ABAF-981302CD7AC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47ef788c8d903e7ba1dbeb4b94680ca79c7a6598","datavalue":{"value":{"entity-type":"item","numeric-id":3335004,"id":"Q3335004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106865$ED60C322-055E-4288-8016-FC143F5A4A59","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dcf2016d6229d259a3d320ed85bab2d7671a17a","datavalue":{"value":{"entity-type":"item","numeric-id":1106863,"id":"Q1106863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"924fe9ba9ba35ee622d1d31b7028041bc35a6920","datavalue":{"value":{"amount":"+0.8892812132835388","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":"Q1106865$08CA000E-609B-4A60-8BBB-48790BA28C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5420ef410220cf74704bda451d24b8a0dee7e471","datavalue":{"value":{"entity-type":"item","numeric-id":1077441,"id":"Q1077441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30c58df6c543bc4a8f48569709592e15bc2e15c2","datavalue":{"value":{"amount":"+0.8608431220054626","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":"Q1106865$7FDA9485-0BEA-4823-BE92-64BB91DD9DDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c5d71db8c045baf77507a3a32e1d385592148fa","datavalue":{"value":{"entity-type":"item","numeric-id":753673,"id":"Q753673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"037c598c21ab678aaf9a2139cd8b4b2738de9e3d","datavalue":{"value":{"amount":"+0.8537862300872803","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":"Q1106865$83B86182-14B1-4E73-AE5C-B71E302B847D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51eeff64f65f4d72594430123ac56a95692418b8","datavalue":{"value":{"entity-type":"item","numeric-id":4697213,"id":"Q4697213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91608275549ed3bcfc5b15fe4d23adda948470c9","datavalue":{"value":{"amount":"+0.8293390274047852","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":"Q1106865$9AB80D12-2AE4-4345-9D54-C195F5D495D2","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":"1d579be449102194ce4ec7494382c20dd6497014","datavalue":{"value":{"amount":"+0.8213871717453003","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":"Q1106865$BCA3CB44-FDD4-4A56-A864-A9EBAB8B0704","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1106865","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1106865"}}}}}