{"entities":{"Q3974856":{"pageid":6004753,"ns":120,"title":"Item:Q3974856","lastrevid":108757127,"modified":"2026-11-10T04:05:16Z","type":"item","id":"Q3974856","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 17532"}},"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":"Q3974856$1B0DD2A3-01ED-47DF-9174-18C5494A1AD9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8aa3113d97d39a00494afc4f6894e57f0537cf4","datavalue":{"value":"0756.68084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3974856$8D15548C-A5A0-4C4A-B00B-F1EA1C6A9F1D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb68d9de22321af7fb543db220c0a16a741857c","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3974856$19C73904-4C44-4E85-AF31-8FCA98C5BC62","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3974856$2300CD07-9F08-4109-A45D-BD6B1C6A2316","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3974856$A060C7C6-9F97-4C3D-839D-1F169C05903E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3974856$A017E83A-9E52-46CB-8A35-71A38D8BDF6F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"47c4ce77c0af44c229821f6cb22f517c303453cd","datavalue":{"value":"17532","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3974856$F3E8A1A8-BBCE-4A23-B565-758BE7269262","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f87a49764ffa977187bf36e4f4234e9b658a5d6f","datavalue":{"value":"biconvex graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3974856$383B79FE-D9DC-4AA4-983C-E748099C774F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad4b7ee9a8fa047c13594b6343ea52da72607129","datavalue":{"value":"rectangle independent point sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q3974856$4AC7D1DD-0058-4C9C-8D2A-8B998C541E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecf0adc8b114312999f3f81284f0317fdf482693","datavalue":{"value":"rectangle covers","type":"string"},"datatype":"string"},"type":"statement","id":"Q3974856$53392D92-F212-4D4C-AB2B-AC92D785A46F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d752149583d7ee9659fd619df8f643680fb8b09","datavalue":{"value":"bipartite permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3974856$95336A3F-8674-4782-BBCE-8B29E051F769","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":"Q3974856$20425667-2867-409F-90CB-439DFCE40DD1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77164074cd49d7a08ce68b2336125fb4f6bd40b6","datavalue":{"value":{"entity-type":"item","numeric-id":3009778,"id":"Q3009778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"798470e7a3960bea88a84759096fec2e52783bee","datavalue":{"value":{"amount":"+0.7953805327415466","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":"Q3974856$69F51383-A7CF-4ACD-A366-CBA235CBC443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf05aa25834797be0dfdc5d96092e6e1282fce17","datavalue":{"value":{"entity-type":"item","numeric-id":3984738,"id":"Q3984738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85308f5c7cde40984bb1ecd4c0383e137afed091","datavalue":{"value":{"amount":"+0.7854810357093811","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":"Q3974856$4C759DE7-BB95-4C07-B2A3-03CF4466447F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bcb32a6d6e93041331c2cf42749687a90b2ca5d","datavalue":{"value":{"entity-type":"item","numeric-id":5935840,"id":"Q5935840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae18f547f3b9001d03b92440ea8b231f99df895b","datavalue":{"value":{"amount":"+0.7373530268669128","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":"Q3974856$8290847C-2B2D-4974-8927-CA5A52EFD306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88f1852be67bf67b4f62aef7d8604215802b64fe","datavalue":{"value":{"entity-type":"item","numeric-id":3719852,"id":"Q3719852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2dd0961a07e888a68c18289bed5938d9ecc2305","datavalue":{"value":{"amount":"+0.7289316058158875","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":"Q3974856$FEDD398F-EA4D-45B5-BCFD-5F2067618EC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50e30df44fb504a9c53d2deb259f3f6e8f76ab5b","datavalue":{"value":{"entity-type":"item","numeric-id":1570816,"id":"Q1570816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"797d6b64284e721947261b30d0eb5c0ff27544af","datavalue":{"value":{"amount":"+0.7271418571472168","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":"Q3974856$FD86B18C-8AEC-4BE7-B8D8-DD7E0E60A0B5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d76062da392f0e4086b18e54a0a3585e4fb98383","datavalue":{"value":"10.1007/3-540-51498-8_7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3974856$ABE53DFA-F0C8-439B-9D67-87EDF91DB921","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"858bd23ba871e065192ea45e0143072465d76fb2","datavalue":{"value":"[For the entire collection see Zbl 0726.00019.] We show that the jump number of biconvex graphs (a subclass of chordal bipartite graphs) can be determined in polynomial time using several reformulations of the problem and a duality relation between rectangle independent point sets and rectangle covers of rectangular regions known from a result of \\textit{S. Chaiken}, \\textit{D. J. Kleitman}, \\textit{M. Saks} and \\textit{J. Shearer} [SIAM J. Alg. Discr. Math., 394-410 (1981; Zbl 0506.05022)] and \\textit{D. Franzblau} and \\textit{D. J. Kleitman} [An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals, 16th STOC, 167-174 (1984)]. This solves the jump number problem for biconvex graphs by means of computational geometry. Furthermore for bipartite permutation graphs (a subclass of biconvex graphs) the rectangle cover approach yields a greedy solution which is faster than the dynamic programming solution given by \\textit{G. Steiner} and \\textit{L. Stewart} [A linear time algorithm to find the jump number of 2-dimensional bipartite orders, Order 3, 359-367 (1987; Zbl 0622.06002)]. An optimal rectangle cover can be determined in linear time using the geometric description of the region or the defining permutation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3974856$515BCEDA-A429-4320-9E83-D24ADAB2FFF7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3974856$B79251C4-DEE4-44F5-B192-619A01ECA15F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3974856","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3974856"}}}}}