{"entities":{"Q1106863":{"pageid":1117612,"ns":120,"title":"Item:Q1106863","lastrevid":49194580,"modified":"2026-01-06T18:06:17Z","type":"item","id":"Q1106863","labels":{"en":{"language":"en","value":"Computing the bump number is easy"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4063158"}},"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":"Q1106863$240FD540-A0E7-496C-BE3F-1CE73E1CE147","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"97cd3a1a087b7849bb8b0671344a9b39143da81a","datavalue":{"value":{"text":"Computing the bump number is easy","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106863$383DA9DF-5D78-4D49-A4A1-A4B891466226","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d909f6f956d2068c9e51a242ea676b6c65d4c99c","datavalue":{"value":"0652.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106863$0A7F5214-DAE5-4391-996D-269F7B8249BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"60e2a49cf8edc718ae30886632752bc1ba230497","datavalue":{"value":"10.1007/BF00337617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106863$7317B5E6-4C63-44A1-8C57-1C34F4FC096F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1323f2124471b30d48a6c6e6f1ae8bcd00448bd","datavalue":{"value":{"entity-type":"item","numeric-id":207372,"id":"Q207372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$C43B2B58-9F02-46C4-ABAD-11897DFD3067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1814572f6f5cc98a1bdac6b4fecbd84381c8ff3","datavalue":{"value":{"entity-type":"item","numeric-id":187128,"id":"Q187128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$2F4A920E-3BD2-4B19-AFF0-356114CE5B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"de64f458823e8aad8ed9f5e383ceb62ca3f7e758","datavalue":{"value":{"entity-type":"item","numeric-id":406261,"id":"Q406261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$274D61AA-CBC8-4A07-B5F0-89D054C1A0AD","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":"Q1106863$98C3ECAB-D048-418B-A539-83786C964B7E","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":"Q1106863$9AA45CB1-371B-42B9-933D-6E0F69FF8C02","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bff4c1b0e07161c06e345ea5a71ecef61f243d9c","datavalue":{"value":"The bump number b(P) of a partial order P is the minimum number of comparable adjacent pairs in some linear extension of P. It has an interesting application in the context of linear circuit layout problems. Its determination is equivalent to maximizing the number of jumps in some linear extension of P, for which the corresponding minimization problem (the jump number problem) is known to be NP-hard. We derive a polynomial algorithm for determining b(P). The proof of its correctness is based on a min-max theorem involving simple-structured series-parallel partial orders contained in P. This approach also leads to a characterization of all minimal partial orders (with respect to inclusion of the order relations) with fixed bump number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106863$D948F655-411B-42C9-B0B0-7535C0ADA107","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106863$9CDC8D19-CF67-4C14-BE72-7F8EB091D9AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106863$C4C4E389-CB26-4E2D-A14F-68D3360385B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106863$33984026-7F25-4A15-AF93-7E9BC693CB57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106863$B963D3F0-FA23-4457-A6C5-EC80C475C4CC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c1781fce18683b4bb613aedd90731dd4b72d692","datavalue":{"value":"4063158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106863$E2DD042B-2BBB-4EC6-B056-0B9AEA932D11","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45ce782da195090588818a066a1f104d5fd148cf","datavalue":{"value":"bump number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106863$7E13A440-E0AF-4A86-920B-EBC250CF751D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"311b860a0597dd249b584149fd2ab2e7e5bfa5ec","datavalue":{"value":"linear extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106863$206C1BB5-0D1F-4DBF-AD92-C51B7CA678D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00497cf8521f215fb0c2c8b8c2d581b2e18ae6ae","datavalue":{"value":"linear circuit layout","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106863$DAFDDB09-8163-4D1F-970F-73A505C36590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2cffdd979b8a15b91e3b3c526e7ba6e6281c14e5","datavalue":{"value":"number of jumps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106863$46F9363E-DF34-4EA3-99E2-5B07DC6EAB48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106863$914D1578-32D3-43C3-9237-3A007EA45C1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106863$997F0671-00FD-4EDB-BB28-AA7CC387F34A","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":"Q1106863$EB2D260E-8728-48DC-A6BA-48733696FEE2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"38e6434a58be942dc8c6f0fde7619ad403e37532","datavalue":{"value":{"entity-type":"item","numeric-id":5646916,"id":"Q5646916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$4D2EDB5F-C067-4362-81A1-B53354D9FC8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc83ab978766094852e17270c60fbe497adf479b","datavalue":{"value":{"entity-type":"item","numeric-id":1078213,"id":"Q1078213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$01F37E55-3636-46FA-9272-6456C5F19A9B","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":"Q1106863$79B15F43-D491-43C3-8F70-3FFCFAD46B8B","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":"Q1106863$052B4EEF-DF2B-4A5A-BF62-42CA0E6ACD16","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":"Q1106863$B755BA40-6317-4305-B2D2-BFD7C7F1626F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$C063E196-ADC0-4B25-BFB2-7736693095D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60934b31a67546c38059b4ae3bc784c6d20aa6aa","datavalue":{"value":{"entity-type":"item","numeric-id":1106865,"id":"Q1106865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$B8E84B32-717C-45E4-A9BC-8190767E9D7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f961d081cfc599e15e8c9a1c8f9b56025d3ff564","datavalue":{"value":{"entity-type":"item","numeric-id":1122595,"id":"Q1122595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$429683A2-4C8F-4A0F-A31D-AC20B6BF9878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de15d26ad6d10743bee1267fea360305492a057e","datavalue":{"value":{"entity-type":"item","numeric-id":1114719,"id":"Q1114719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$D60EDB44-CF0E-4B0A-8A12-F7B39FD93225","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eb25086495becbf044bff64d79baa50a4862548","datavalue":{"value":{"entity-type":"item","numeric-id":1097902,"id":"Q1097902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106863$0F63C2DD-6C80-432D-93FE-33BB4B5A1D91","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b34a315ccf233290e1c3a7aa8805dc0d2bee89a","datavalue":{"value":"https://doi.org/10.1007/bf00337617","type":"string"},"datatype":"url"},"type":"statement","id":"Q1106863$6974573B-973B-4E9B-8FC2-674568F79131","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"00af5acbf8428e56a45da04d1f54f27d6ad1a1b6","datavalue":{"value":"W2088579252","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106863$EC535CC0-57D2-4541-BA93-23F6FF943A06","rank":"normal"}],"P1643":[{"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":"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":"Q1106863$02EF28B7-6071-4463-B7A5-3946E633A752","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":"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":"Q1106863$8397D8F8-337F-4382-8ABD-F1915763C1F2","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":"4bc189a94b949037002a412c0d2099c3b5a02604","datavalue":{"value":{"amount":"+0.8193780779838562","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":"Q1106863$32711613-5934-4A5F-A7E5-3470D82599E4","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":"8c403bdc31aab636b2370e821944dd372ef17948","datavalue":{"value":{"amount":"+0.8055678606033325","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":"Q1106863$E515D63D-D7C0-4A7D-873E-D96AE0303675","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":"a9e8dcc01385fdb8ba35be37a95b79578f24b3b5","datavalue":{"value":{"amount":"+0.8023127913475037","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":"Q1106863$76F11EF3-3E48-460C-BFBD-5F8BA822D6C6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1106863","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1106863"}}}}}