{"entities":{"Q1111581":{"pageid":1122330,"ns":120,"title":"Item:Q1111581","lastrevid":49220977,"modified":"2026-01-06T19:17:29Z","type":"item","id":"Q1111581","labels":{"en":{"language":"en","value":"On minimizing the jump number for interval orders"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4075133"}},"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":"Q1111581$BCD17BB5-33B6-4D84-A4CD-09AE413880B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2109ca361d446a20b62c2875acd80fe56d718eb9","datavalue":{"value":{"text":"On minimizing the jump number for interval orders","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111581$AB64CAEA-1005-41ED-BBE1-961EFE085717","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f484852c19a6c2d9ebc3041f5c682d4977c60054","datavalue":{"value":"0658.06001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111581$4A544F4A-5BF9-45B6-AB5A-51C7A2D97E85","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e40ec776750d80e747c4a8acd16072682122015a","datavalue":{"value":"10.1007/BF00714476","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111581$6E9EDAD1-2818-46EF-A463-EAB23AF313D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"82a039165efe5e96e7073de9040557515422975c","datavalue":{"value":{"entity-type":"item","numeric-id":1111579,"id":"Q1111579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111581$F18B2D81-D2F4-4FCC-8C14-8119206F835D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"717d1316694a09b72da7b907a09f6b8bfbc28007","datavalue":{"value":{"entity-type":"item","numeric-id":603887,"id":"Q603887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111581$9A56E9CD-83EE-402F-BB3A-980CD4CCDEF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a7eba421eb72816497f5502ab63bcc0b239e1408","datavalue":{"value":{"entity-type":"item","numeric-id":686165,"id":"Q686165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111581$6772D9B3-2E7E-492F-9135-5233F2122697","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":"Q1111581$C70365C5-7514-4AB5-829D-A7A1777CCA18","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":"Q1111581$5CE20E60-B5C9-4C83-9015-DF6E7B0979E2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"217e2a3362e0193876d0abc9a66fb5f49d246c16","datavalue":{"value":"In ``the greedy poset problem'' one seeks to determine those finite posets P whose greedy linear extensions are jump-optimal as well. The Rival-Zaguia 1983 result to the effect that the sets of greedy linear extensions and jump-optimal linear extensions are identical for N-free posets is probably the best known result along these lines to date.    This paper is another installment illustrating the R-Z approach as applied to a particular and important class of posets, viz., the interval posets. An important 1986 result of Rival-Zaguia characterizes general greedy posets in a somewhat complicated way. By transformation-refinement of the arguments needed to obtain this result (Thm. 1 in the present paper) and some useful specific lemmas, the authors demonstrate in the proof of Theorem 2 that an interval poset P is greedy if and only if every N in P is completed from above or below. Here \\(N=\\{a,b,c,d|\\) \\(a<c\\), \\(b<c\\), \\(b<d\\}\\) is ``completed from below'' if (1) a has at least one lower cover, (2) for every x covered by a, the order on \\(\\{\\) x,a,b,c,d\\(\\}\\) is such that \\(x<d\\) (in P), (3) whenever x is covered by a and t covers x, \\(t\\neq a\\), then \\(t>b.\\)    The terminology ``completed from above'' has an obvious dual meaning. Using Theorem 2 one obtains a computationally effective means of solving the greedy poset problem for interval orders. The problem is known to be NP-hard otherwise.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111581$11F15010-F94F-4E01-9074-39A1B1854924","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111581$A652D658-01A5-40C9-82FB-DB1DE4C3312A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111581$D4AF09BA-2167-42B8-9643-FEED4659D25E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111581$61D28A9F-CB2B-4750-9339-943A209E68D3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"da7a40b790d3c8bf61248e5e529864c57f1e9a36","datavalue":{"value":"4075133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111581$B4B6E425-0DDF-4D70-94BE-FD4FFFFD83C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8fdbede0e55799b154cb298ccb951db472fb2e85","datavalue":{"value":"jump number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111581$297AD50F-8709-42F8-88AC-9F7E2BA471C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8da4f4f099d21d3294017ea4e7fd25b8c643bbd9","datavalue":{"value":"greedy poset problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111581$1237FAD7-DE38-4B7E-A795-B61A48A333D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78679407d0c379d5b2a50f85259e5f65d5499ca8","datavalue":{"value":"greedy linear extensions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111581$10ACBEBF-D81A-4D59-84BA-9A7967AC3060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a3dbb159e0d542ba48bcedd4712caa5222523a7","datavalue":{"value":"interval posets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111581$62CF0AF7-794D-481A-8DB1-7C1EAEC7A264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62d18420b0848a4c0300452d10ba1f75d74dc0e1","datavalue":{"value":"interval orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111581$DC07A059-838C-4E17-A3CC-3497DAFB3CED","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":"Q1111581$9F7B1CB8-9743-43E6-BE1D-BC7820C5F57D","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":"Q1111581$47986D32-4F32-45AB-AB9A-DAB6FA488EE0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e5752fee4b6ef183d872e55d88367ad22d90dde","datavalue":{"value":{"entity-type":"item","numeric-id":1087567,"id":"Q1087567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111581$35F2C625-1287-4238-96A6-34A1E05066C6","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":"Q1111581$5711C353-639B-4E3D-A513-564BE6E50514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5805238c0fe4905dee22c3e5f8aa9b182c98878a","datavalue":{"value":{"entity-type":"item","numeric-id":1087566,"id":"Q1087566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111581$CDF5C9BE-0B8F-4DE6-A552-9F05B87B798D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"573d580db937b144c4e3c67d0ca4132151edf27d","datavalue":{"value":{"entity-type":"item","numeric-id":1821122,"id":"Q1821122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111581$16CDE7C6-ED4C-4698-90F6-86150299CBE6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2a4bc2637d65821aac6f2b5041f0266bfba01443","datavalue":{"value":"https://doi.org/10.1007/bf00714476","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111581$0411C30B-AC7C-49B0-968B-172C33B24499","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"502873aac3fc53a5d1759c42bc74a00f940f635e","datavalue":{"value":"W2054170773","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111581$D4ECC1E9-C0FC-4A83-8DFB-232DBB4A7860","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65928de81889d0e28b2cbfc5754b1af9b8afc457","datavalue":{"value":{"entity-type":"item","numeric-id":1104949,"id":"Q1104949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0ed753c937eb41c943d9d6444e9c4bd2f86ae2f","datavalue":{"value":{"amount":"+0.8397108912467957","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":"Q1111581$614C55D7-92FC-42A3-B429-1BC4F38CAAEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"228ea1e2e82f9bc4ebe200a788ec67510b72cd37","datavalue":{"value":{"entity-type":"item","numeric-id":1061150,"id":"Q1061150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"144a792bf317446e47ec667d7541152acf404395","datavalue":{"value":{"amount":"+0.8366060853004456","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":"Q1111581$78E42500-55D7-498C-9A53-136C38C4394D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdb2541f66ecf6628e2e4a7ff44ada5639c07941","datavalue":{"value":{"entity-type":"item","numeric-id":1097902,"id":"Q1097902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46a933ce892f3483b38067b2a8ec82c8fce4dab3","datavalue":{"value":{"amount":"+0.8359168171882629","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":"Q1111581$82D82D7E-632B-40FC-A11E-2DAF3D7ED671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b64c839935a2acc0484476bed839fe735a4b339b","datavalue":{"value":{"entity-type":"item","numeric-id":921022,"id":"Q921022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9321326d5e88db7c73eb7d9b470e6991770c24e","datavalue":{"value":{"amount":"+0.8306438326835632","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":"Q1111581$F0CE76ED-3D60-4D52-B32A-8C8ABCF52CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"173065e64444e0ca3996fce99dd1165429c0a1af","datavalue":{"value":{"entity-type":"item","numeric-id":1894377,"id":"Q1894377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97fbfb4a63bee30f36b3cb3f7b4c71645cd4e723","datavalue":{"value":{"amount":"+0.8270951509475708","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":"Q1111581$E79B4528-9018-49F7-9D00-ECEA0ED4F5B3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1111581","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1111581"}}}}}