{"entities":{"Q1077441":{"pageid":1088193,"ns":120,"title":"Item:Q1077441","lastrevid":48946792,"modified":"2026-01-06T06:58:26Z","type":"item","id":"Q1077441","labels":{"en":{"language":"en","value":"Minimizing bumps in linear extensions of ordered sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3957180"}},"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":"Q1077441$36294D2D-8F9A-4180-999A-E6B13BE36B5A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a7a0259de5be662c54d4a65f37666095bf57820e","datavalue":{"value":{"text":"Minimizing bumps in linear extensions of ordered sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1077441$28924496-42FF-4D2B-B3AF-15A1AA39B13A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"946d235332e243514b117e20a571229ee1164da5","datavalue":{"value":"0595.06004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077441$51CC8B09-3725-4F65-B4E0-97AD70F6710E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"df6a0bfea431e699ed06d13bb6aaede6241544f7","datavalue":{"value":"10.1007/BF00403405","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077441$1E1F21EE-8B26-4DDC-9960-696E5F6C1C98","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6077ee98d9630e9737fc0514d33b3b5053e02ef2","datavalue":{"value":{"entity-type":"item","numeric-id":221502,"id":"Q221502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$32D5EDF5-5341-44D8-AEEB-230FCED1FE21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0c6b67abf5ac1238d97c400bd3ace6fd2896a3b","datavalue":{"value":{"entity-type":"item","numeric-id":177535,"id":"Q177535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$0AAA28B4-A01F-4EB1-9FC2-68482756BFFE","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":"Q1077441$3DD2591E-4D39-4C93-875E-33E526920D0C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1077441$83F98785-4A5E-40C3-8C9E-407DE68DB1E9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d59a4c137de4b25d443aa3e099d031cc126dab0d","datavalue":{"value":"Given a finite partially ordered set P, there are many ways of imbedding the set into a linearly ordered one respecting order. Whenever \\(a<b\\), but a is incomparable to b in the original order, one speaks of a ''jump''. Up to the present there is no known efficient algorithm to linearly extend a poset, minimizing the number of jumps. It seems to be known that determining the so-called ''jump number'', i.e. the minimal number of jumps that must occur in any linearization, is NP-complete [W. R. Pulleyblank (to appear)].    The paper under review takes the opposite point of view by calling a ''bump'' an occurrence of \\(a<b\\), with \\(a<b\\) also in the original order. The problem is now to minimize bumps, which is equivalent to maximize jumps. (The puns involved in this choice of words are unfortunate, as they could never be translated into another language.) The authors study some possible algorithms for this problem. As in the case of the first problem, there are always some sufficient conditions on posets to guarantee optimality, but no necessary ones seem to be known.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077441$E6FE699C-E1FF-4398-B7BA-88036AD58549","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077441$FE5BF9D3-1BF6-4944-9570-389E2CF8852A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077441$49952015-EA02-47D7-BD5B-73C8B655B6B3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7dbff0827b76b2b55e436881a8cdecca41ada09b","datavalue":{"value":"3957180","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077441$8BC7B551-8B03-4650-991F-F2CF287DF364","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa00b05ff385f9b30b2d792bdb87a20d25fca3cc","datavalue":{"value":"finite partially ordered set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077441$81A97A75-03F3-467E-8ABA-90C8B2EDAD2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8fdbede0e55799b154cb298ccb951db472fb2e85","datavalue":{"value":"jump number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077441$E9D41784-C01C-4329-A86E-7366F26DEF3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"081b79b4adfd295e5dab936c22cabd29ef04eede","datavalue":{"value":"linearization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077441$6CFF46BF-798E-4FD3-A754-7BE8BD0B76A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077441$CC3FD4D1-6041-483D-A874-17368F7EF19E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6f1247b3b75de3a85a07df92e18a12bfc1ec7213","datavalue":{"value":"Q39753279","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077441$54323D99-94BB-4E95-9C1C-F797C65E3D6B","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":"Q1077441$D682930D-A2B6-4136-BDF1-D4D81537185E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8945007f067454dde27425b4128d7b94e6ccb98","datavalue":{"value":{"entity-type":"item","numeric-id":5675506,"id":"Q5675506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$AD4B959F-017B-4FB3-B210-F03038D1FAA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"264e1cc4d5b5edaf92740589f5202d1c1d957871","datavalue":{"value":{"entity-type":"item","numeric-id":762183,"id":"Q762183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$F018E733-5A26-40EE-987A-36C979D2A8C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f159aacfddbc201f6b79ecf804a940116897f8f","datavalue":{"value":{"entity-type":"item","numeric-id":1061150,"id":"Q1061150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$F93F1284-B539-48CE-9670-8D335B869ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33ee070898d43be9d6b72653b759a3905d4e320e","datavalue":{"value":{"entity-type":"item","numeric-id":3691788,"id":"Q3691788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$45EFAE0E-05DA-40DC-AA02-CDA2D4445209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c89eaca0c637703f9ae0cc66672c6857df95bf8b","datavalue":{"value":{"entity-type":"item","numeric-id":802585,"id":"Q802585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$96FCF67F-9B3B-49DC-8CE4-ECAD17F35B93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bce677a9c061b16210c3b75fe5d9808dd9ed326","datavalue":{"value":{"entity-type":"item","numeric-id":1060230,"id":"Q1060230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$BAB810D4-65DB-48DB-B44F-1D474AF06D36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b48d8a5caa0be18e258f0b05c17c265eec9e1020","datavalue":{"value":{"entity-type":"item","numeric-id":1820992,"id":"Q1820992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$327F5E65-954C-4E42-BACA-5F683E4EA751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f35b03f4cee5a1c0ecf945160be55ecd9139027e","datavalue":{"value":{"entity-type":"item","numeric-id":3233621,"id":"Q3233621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$8AFB7B96-AFD2-4ABB-B8CE-E1C931131622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed18cf40bc2621864c4847f35e0a398fd66f6909","datavalue":{"value":{"entity-type":"item","numeric-id":5621253,"id":"Q5621253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$EC0689E9-29C5-4E87-A61D-93D2D789EC7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d4c3394fe33a803d44b9613be7e42b3f4c68ee4","datavalue":{"value":{"entity-type":"item","numeric-id":3674720,"id":"Q3674720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$2A8F91D4-0114-4D7F-94C6-3AFF7250614D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d932d2dd9959d01e52a083bc9b3ddf17f04db94","datavalue":{"value":{"entity-type":"item","numeric-id":1092072,"id":"Q1092072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$60F027CD-51ED-4420-9B64-BBC1D0F027BB","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":"Q1077441$7BBD3BFD-8755-488F-8E2C-AF50D79EF9C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e583c6fcdec1f2af46629c50832b9198e1a4430b","datavalue":{"value":{"entity-type":"item","numeric-id":1057289,"id":"Q1057289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077441$B759E570-78DB-4BB5-BE57-05C991C4FA35","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"43bfa5c4aa2a9483ed5b9c59d39509e9e3f604eb","datavalue":{"value":"https://doi.org/10.1007/bf00403405","type":"string"},"datatype":"url"},"type":"statement","id":"Q1077441$3E738F44-0610-444A-9DD2-2B48A5AC1574","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6871a53a064ef4bd31341be890b6c343b6a05c91","datavalue":{"value":"W1983875646","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077441$BCA66793-4E7A-4AFC-A16B-3E391FA7E53E","rank":"normal"}],"P1643":[{"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":"a25cd1efb5cba9b44f30a1498b4e923db5d76b84","datavalue":{"value":{"amount":"+0.8703542351722717","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":"Q1077441$BF339CA7-B14A-49C7-A423-3DB2B813497F","rank":"normal"},{"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":"50a944c04bbf10bab1457078617feca4192d2330","datavalue":{"value":{"amount":"+0.8610442876815796","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":"Q1077441$1763FE53-8EFD-498E-95C7-253BE460CA2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33715da112eb037cd1f0758ff7046e81da2ef485","datavalue":{"value":{"entity-type":"item","numeric-id":1106865,"id":"Q1106865"},"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":"Q1077441$E52A1672-67F4-4127-BB25-F4F20D16F647","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6c116b7e8f01cfc3cf94a3a71d0ba118207d636","datavalue":{"value":{"entity-type":"item","numeric-id":1820992,"id":"Q1820992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a4496c1aa35f6b48ecaf732d9b75d9f574ee797","datavalue":{"value":{"amount":"+0.8575406670570374","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":"Q1077441$D0FF91A0-F776-4EE0-B45F-65CAAC33389E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2323c7356e344aae435b2c8af13c1fe5aac54dde","datavalue":{"value":{"entity-type":"item","numeric-id":1122595,"id":"Q1122595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27450f71c31326046d5870aeb3ab01bc0658fc2c","datavalue":{"value":{"amount":"+0.8547013998031616","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":"Q1077441$327BE875-A2BB-42A8-8E7F-1E22226C8696","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1077441","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1077441"}}}}}