{"entities":{"Q921022":{"pageid":922870,"ns":120,"title":"Item:Q921022","lastrevid":65397408,"modified":"2026-04-12T02:18:59Z","type":"item","id":"Q921022","labels":{"en":{"language":"en","value":"A 3/2-approximation algorithm for the jump number of interval orders"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4164922"}},"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":"Q921022$21F54EEC-77E9-4334-927C-1DF010556651","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d3db07c279d79fcb94e4ecc89015e284543b4751","datavalue":{"value":{"text":"A 3/2-approximation algorithm for the jump number of interval orders","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q921022$03AD9043-6EAA-48FA-8319-A49635F32E19","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"128afcd32d3f7841d81f983d765c2c74b2dc93b5","datavalue":{"value":"0709.06001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921022$AA35F27A-686E-4E3E-89FC-F4561794D8E9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c69b4c0aae93d453acd8ebad81c9e9e7899a864","datavalue":{"value":"10.1007/BF00346129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921022$ED8A0916-679D-4248-B633-8BF5411ED110","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb43e4c4f1b169e3803b8b6726a3b03e15c78164","datavalue":{"value":{"entity-type":"item","numeric-id":170482,"id":"Q170482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921022$E712BEA9-4F2B-4965-BD3F-782F29D34854","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":"Q921022$78412270-F3DB-4B1C-82E2-2CD03DFE4AB5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q921022$4BD7C9F4-0FAB-4D9D-82EE-E791A2B425FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bcf10bf11f10a7579333a189dd1f1f56749c7a38","datavalue":{"value":"Let P be a (partially) ordered finite set. A pair of two consecutive elements \\(x_ i<x_{i+1}\\) of a linear extension L of P is called a jump if \\(x_ i\\) is incomparable to \\(x_{i+1}\\) in P. The number of all jumps of L is denoted by \\(s_ p(L)\\). The minimum number of \\(s_ P(L)\\) is called the jump number s(P) of P \\((s(P)=\\min \\{a_ P(L):\\) L is a linear extension of \\(P\\}\\)). An optimal linear extension L of P has the property \\(s(P)=s_ P(L).\\)    In this paper some algorithms constructing linear extensions are developed, especially for interval orders, which are ordered sets P whose elements are in a one-to-one correspondence with intervals on the real axis \\((x\\leftrightarrow I_ x)\\) such that \\(x<_ Py\\) iff sup \\(I_ x\\leq \\inf I_ y\\). For an interval order P a linear extension \\(\\Lambda\\) is constructed with \\(s_ P(\\Lambda)\\leq (3/2)s(P)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q921022$52673A86-F33B-46C9-8124-0A1C93698C34","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921022$F44FBD35-003D-448F-BB9F-F2F54AC2658B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"104f257a0254c7069cf71b576e8b550a1d2ab49f","datavalue":{"value":"4164922","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921022$321C129E-80A0-47D9-974C-57CD7087F9DB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q921022$98ECC76A-66DF-441C-91CF-73345D00297E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3cfdb6b2705cbfa4f5325db3793e5c8fd944916","datavalue":{"value":"optimal linear extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q921022$C263190B-94C4-4F43-AD8E-6BD7FD3623EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8fdbede0e55799b154cb298ccb951db472fb2e85","datavalue":{"value":"jump number","type":"string"},"datatype":"string"},"type":"statement","id":"Q921022$2F9049B4-5FFB-4FB9-9B5F-EF1F78CD61E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62d18420b0848a4c0300452d10ba1f75d74dc0e1","datavalue":{"value":"interval orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q921022$81713A78-0204-457E-9884-5C09DD1834DD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"11c6ee72db6a1595c302ec495a8cbae324d7c3a3","datavalue":{"value":{"entity-type":"item","numeric-id":551312,"id":"Q551312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921022$361EFDC9-B854-44D1-9AB6-87DB4DEB0DB1","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":"Q921022$638D4CA0-8FD6-4817-8971-418FAD697005","rank":"normal"}],"P223":[{"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":"Q921022$7ABD11AF-C277-466F-A92C-48E62E0A0E26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"303e345f747f79e501d44b36aac461c0078c7ee5","datavalue":{"value":{"entity-type":"item","numeric-id":1064975,"id":"Q1064975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921022$C83019BC-B84D-49EC-B5F2-39CC695EC790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7719de6c339bb9d4088f30d5f516e35f5c2b87f","datavalue":{"value":{"entity-type":"item","numeric-id":3694689,"id":"Q3694689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921022$34DA37D1-DEEC-41B0-AAB6-E18A7166B90D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adfb27f83a5850856e9495cf6d580046b643d442","datavalue":{"value":{"entity-type":"item","numeric-id":1111581,"id":"Q1111581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921022$33D178DE-7FDA-44DC-AAD8-5F464552D983","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":"Q921022$A7343AE4-2210-4E0C-846E-94B571637087","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":"Q921022$431BD5E7-B09C-4B6F-A808-704DF7DF06FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45bf10a9f666727577e0ebdf94e82c9ce3bd7c24","datavalue":{"value":{"entity-type":"item","numeric-id":1090688,"id":"Q1090688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921022$D9F1F97F-E8D9-4388-9623-D215ACD509C6","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":"Q921022$2FB0E038-98D7-4C8B-ACD9-D439367B45F0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b5bc11d1951baf370989be9739528b027b7c342","datavalue":{"value":"https://doi.org/10.1007/bf00346129","type":"string"},"datatype":"url"},"type":"statement","id":"Q921022$1D85617C-2A09-450C-A83F-C5E2193F8AE2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e42560ba00107749759a244b9f65325922117252","datavalue":{"value":"W2078314359","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921022$CBAA51B1-D50E-40F0-ADBD-31ABECAA2282","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e98dec7dbd89a3a825ed0bcebe43b7a42ad5427","datavalue":{"value":{"entity-type":"item","numeric-id":391978,"id":"Q391978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98c5f076aacc4f8ae0088d65d5f38141493b2bbe","datavalue":{"value":{"amount":"+0.8785347938537598","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":"Q921022$2C2344E2-B591-4A6C-A8BD-9544A14F16D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e27daee5d7c0708715e35129e1e17d73a3250c1","datavalue":{"value":{"entity-type":"item","numeric-id":1898347,"id":"Q1898347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5cce0460c4b275092ef69c6ed759535eb77bace","datavalue":{"value":{"amount":"+0.8643947243690491","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":"Q921022$DB1653FF-90FD-4DD0-B095-C83A0DDF5D9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d4c0cd8f9c677d1e5d209b59cd5fb6a591b51da","datavalue":{"value":{"entity-type":"item","numeric-id":1818782,"id":"Q1818782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"652795e391f1779f5d165440a05909b2af0c0dd2","datavalue":{"value":{"amount":"+0.8577668070793152","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":"Q921022$0B322BCE-6D5F-4674-85B6-D3498CDC3985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0533bcaeff396372d55af7c85a63b59c3d7b87a5","datavalue":{"value":{"entity-type":"item","numeric-id":3976789,"id":"Q3976789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae2fbaa0fe7bec58c12d076bcd90174706440e42","datavalue":{"value":{"amount":"+0.8546581864356995","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":"Q921022$F51483FD-9C02-453C-9B8D-E1DA6412121F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f092f593c4f508ede47fc18e246977186fd29ed","datavalue":{"value":{"entity-type":"item","numeric-id":1182058,"id":"Q1182058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"720ecf2b0b737173078ccbbe62b7a54ab56c9e3a","datavalue":{"value":{"amount":"+0.850702702999115","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":"Q921022$25CD4B96-20D0-4006-ABA5-C952010C96DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A 3/2-approximation algorithm for the jump number of interval orders","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_3/2-approximation_algorithm_for_the_jump_number_of_interval_orders"}}}}}