{"entities":{"Q1115629":{"pageid":1126378,"ns":120,"title":"Item:Q1115629","lastrevid":49246324,"modified":"2026-01-06T20:28:48Z","type":"item","id":"Q1115629","labels":{"en":{"language":"en","value":"An efficient algorithm for maxdominance, with applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4087043"}},"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":"Q1115629$B6D0CCAE-9981-4C98-895F-E6F474C45778","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a775f183a7b84be7e34af49fd55d3250915db833","datavalue":{"value":{"text":"An efficient algorithm for maxdominance, with applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1115629$7BAE0725-F601-44BD-8179-41474424D06B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b0eb3347b62a713805a3920e3032b8ed310899a4","datavalue":{"value":"0664.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115629$5BD0A017-ADDF-4748-AA2B-674287179E0F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"26e16f14f2a9a52a5b7c2fb2bb6ad34c7dfa1059","datavalue":{"value":"10.1007/BF01553888","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115629$18363B28-7492-448A-9CFE-7425F6EC0FAB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54db673cbb28bd82524949973025fcdaf1d3af32","datavalue":{"value":{"entity-type":"item","numeric-id":522962,"id":"Q522962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$1431A899-F020-491B-A9DE-94C5851679E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97ae1d05248d2d268c19d2f23763f39d29e49e68","datavalue":{"value":{"entity-type":"item","numeric-id":916386,"id":"Q916386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$779620CA-9650-4324-896D-85D8BE26AF04","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$54568CFA-9844-42A4-AE94-84E5EA5B4144","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1115629$ED7B2376-0AB8-46CA-A359-4C504B377790","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6cd11b797254e6dd85580d665d0076e58e5f0660","datavalue":{"value":"Given a planar set S of n points, maxdominance problems consist of computing, for every \\(p\\in S\\), some function of the maxima of the subset of S that is dominated by p. A number of geometric and graph-theoretic problems can be formulated as maxdominance problems, including the problem of computing a minimum independent dominating set in a permutation graph, the related problem of finding the shortest maximal increasing subsequence, the problem of enumerating restricted empty rectangles, and the related problem of computing the largest empty rectangle.    We give an algorithm for optimally solving a class of maxdominance problems. A straightforward application of our algorithm yields improved time bounds for the above-mentioned problems. The techniques used in the algorithm are of independent interest, and include a linear-time tree computation that is likely to arise in other contexts.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115629$49FDC1D9-4BF5-40C9-9AED-9BD1205198CE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115629$FB800F57-0875-40F9-9F25-F98D5FE49E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115629$DD999BDF-98F5-4B73-881D-37143DAA2BC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115629$D9AC1C0C-0F16-49D1-9E8D-9349B183C802","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6298775f41b84f5e075e2169639b77236fd372f9","datavalue":{"value":"4087043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115629$29F4CC3A-683A-4C94-843A-EF764F5183EA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115629$7DD8A72D-2749-4989-A4C0-766DE220A4C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b80d39792cb2cac02d739d0ac44dccfa16c0dd7","datavalue":{"value":"maxdominance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115629$FC211587-B5A5-4F41-9305-B6702E328518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"698781d268edcb63d1ab410f032a99be2b03acba","datavalue":{"value":"minimum independent dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115629$E987753C-F0F1-4AD3-929A-A28CE16BB00B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cba4f4e6b1d6add40394622cbe47bbb0afecf1c","datavalue":{"value":"permutation graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115629$5B8A1E50-24B9-4714-A232-FB7ADCD06E2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fe4c7517961f8d2cf91d64692661ae362c3b449","datavalue":{"value":"largest empty rectangle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115629$48E4CDA0-C732-4077-BF59-772DE5171E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6be45fa3d92ff5488cffe5eac58d1f70301c8e2","datavalue":{"value":"tree computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115629$F4E7650B-13ED-4077-9F27-D5A01EE57433","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":"Q1115629$63FF3E00-4C31-4A71-B752-1D63EAC6C974","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fff3160dcbdd06a215e116759508934efd16dac","datavalue":{"value":{"entity-type":"item","numeric-id":1079570,"id":"Q1079570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$22B5C8FB-F33B-4408-8862-E4D68CDF1FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$56D5BC4D-F3FE-48DC-BA82-F1862B306BAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cad86ad3a1ac50950b1260b4a2c41ef04e6c321","datavalue":{"value":{"entity-type":"item","numeric-id":1117255,"id":"Q1117255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$9B672976-64EA-402D-AB32-5046C2EBD4D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef7e9681d49f2df035d9c81024a2a9090eccea91","datavalue":{"value":{"entity-type":"item","numeric-id":3747743,"id":"Q3747743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$52DD5529-AB5F-4A7D-ABE6-293FE1B4BEB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"654247b383091678755541cf2da8e26416bc2e13","datavalue":{"value":{"entity-type":"item","numeric-id":1140430,"id":"Q1140430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$5562D54B-1CF3-42C4-B2C9-2E28B069B97F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45bd11f1675efb8493ca16666b6e6674ba98a633","datavalue":{"value":{"entity-type":"item","numeric-id":1161300,"id":"Q1161300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$7467EDB6-2300-412D-9872-C99392F1E0C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1901aedd2d8549517a3f77a27b2a3787fa019529","datavalue":{"value":{"entity-type":"item","numeric-id":3731637,"id":"Q3731637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$C9B6241D-BCCF-4E0B-AD2F-29F4AAADAE82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666dd08ea76733c6c9a92f22e1ded54c04865854","datavalue":{"value":{"entity-type":"item","numeric-id":796307,"id":"Q796307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$E9B4C82C-92F6-48FA-BE51-622CA51B120E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"754af2c51721854ffd1227e5e95c695f1e85809a","datavalue":{"value":{"entity-type":"item","numeric-id":582097,"id":"Q582097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$3497A08A-A320-41B9-8FD6-31E1F0D86614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a715219fd6274692c890d4aa82ed20d1406419","datavalue":{"value":{"entity-type":"item","numeric-id":1158972,"id":"Q1158972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115629$FFC42902-9C15-4854-B991-D39167669344","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3670f24acfe00c4d50e21dfd5e494ad4bd2e1d4a","datavalue":{"value":"https://doi.org/10.1007/bf01553888","type":"string"},"datatype":"url"},"type":"statement","id":"Q1115629$4D59C292-D028-488E-BD11-46395E4DDB3D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dfd9d034eb3d3eb4faf2f7534a5e0ff969e506d4","datavalue":{"value":"W1966224002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115629$434245E9-8D7B-48E9-834E-518B87A0FAF1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b15c385203aebd77a69e599a03bad814dafa21d","datavalue":{"value":{"entity-type":"item","numeric-id":2366239,"id":"Q2366239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a38f07bbc5aa79aadaf91b3883d3d343bbb1531","datavalue":{"value":{"amount":"+0.778028666973114","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":"Q1115629$AAB10CD7-DA46-4DBD-833E-AD00A150A548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bba9cd09c15d0075509122bec30783cad0e42ef5","datavalue":{"value":{"entity-type":"item","numeric-id":4352834,"id":"Q4352834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b213d12a8e98a7df65b0127dda85dd479c3cdeca","datavalue":{"value":{"amount":"+0.7764460444450378","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":"Q1115629$1BBB030A-463C-4B88-8922-3EFA8FCC9463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84b70c122185d1d11b8be3f77b830bf1cee719ae","datavalue":{"value":{"entity-type":"item","numeric-id":3990609,"id":"Q3990609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b213d12a8e98a7df65b0127dda85dd479c3cdeca","datavalue":{"value":{"amount":"+0.7764460444450378","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":"Q1115629$585E8EA5-5551-4E22-A259-435D77B351F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbe8e572eac38a17a6d7f449ea7ef6dc8efac281","datavalue":{"value":{"entity-type":"item","numeric-id":750166,"id":"Q750166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54ad141e6b16b32c76ac812d93e7847124f918fd","datavalue":{"value":{"amount":"+0.7727209329605103","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":"Q1115629$11C31762-0D98-49F6-AEEE-72D672C2E66E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa283776381762a152f1402e72e7afad38a05589","datavalue":{"value":{"entity-type":"item","numeric-id":2930264,"id":"Q2930264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f2876c2dc6cfea30628538ee672101fc05a9b81","datavalue":{"value":{"amount":"+0.7707815766334534","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":"Q1115629$E8A6D33D-4C98-42EE-8D0D-1A02CBC92221","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1115629","badges":[]}}}}}