{"entities":{"Q1761500":{"pageid":1772242,"ns":120,"title":"Item:Q1761500","lastrevid":72907512,"modified":"2026-04-14T08:41:27Z","type":"item","id":"Q1761500","labels":{"en":{"language":"en","value":"Minimax trees in linear time with applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6106896"}},"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":"Q1761500$50C29B45-F3F4-47AA-8009-BCAC4D79F6B4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"70a015582758853fb6f7556400df60e484a5d398","datavalue":{"value":{"text":"Minimax trees in linear time with applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1761500$CF9770EE-8426-42CE-9A42-C8511676930D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fe968703a34f41857d9f9a441abd461b64768c7d","datavalue":{"value":"1254.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1761500$09C6583D-7C75-45BF-A42F-7C2E3C6F166B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c0f29833bf40fff5fa7dc4e5775a8ea015827ff","datavalue":{"value":{"entity-type":"item","numeric-id":294944,"id":"Q294944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$C365D68B-A4C3-4E11-8EAF-23EACBF76A3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a86b93d0edba1c47d7a5176784c441eefd7868d","datavalue":{"value":{"entity-type":"item","numeric-id":390357,"id":"Q390357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$CD9AFF27-38E2-4337-919F-F538C0479936","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$D882BFB4-1FC6-4915-A9C4-FA11DCE1A83C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"acc91f928e2b1e0c530416c02d7de319da4a675d","datavalue":{"value":{"time":"+2012-11-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1761500$87455D20-F4D4-4186-919B-248D4ED221B4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"65ce84f787710647e12068b5d038a5a4bbd4a08a","datavalue":{"value":"In a minimax tree for a multiset \\(W=\\{w_1,\\dots,w_n\\}\\) of weights, each leaf has a weight \\(w_i\\), each internal node has weight equal to the maximum of its children's weights plus 1, and the weight of the root is as small as possible. A minimax tree is thus similar to a Huffman tree which minimizes the weighted average of the leaves' depths. Golumbic (1976) [\\textit{M.C. Golumbic}, ``Combinatorial merging,'' IEEE Trans. Comput. 25, 1164--1167 (1976; Zbl 0364.94037)] introduced minimax trees and gave a Huffman-like, \\(\\mathcal O(n\\log n)\\)-time algorithm for building them. Drmota and Szpankowski (2002) [\\textit{M. Drmota} and \\textit{W. Szpankowski}, ``Generalized Shannon code minimizes the maximal redundancy,'' Lect. Notes Comput. Sci. 2286, 306--318 (2002; Zbl 1068.94006)] gave another \\(\\mathcal O(n\\log n)\\)-time algorithm, which takes linear time when the weights are already sorted by their fractional parts.      Main result of this paper is the first linear-time algorithm for building minimax trees for unsorted real weights. This algorithm is based on Drmota and Szpankowski's but, whereas their algorithm uses sorting and binary search, the new one uses generalized selection, as well as a new data structure to test the Kraft inequality. The paper concludes with an application of the presented algorithm to problems in adaptive and semi-static prefix coding and group testing.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1761500$4D3A1430-87C3-4E9B-89F0-953767D504E5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$25EBFB42-0E70-4FD4-B1DC-95FA3ABD52A5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1761500$DFFC99DE-7A41-4E95-B6C7-0C842F09A1FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1761500$FFC299D8-27EB-499D-8E8B-DF6728B5BA53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23eabea2f37667b79d34f4282bba7b6c227abf51","datavalue":{"value":"94A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1761500$259CAD8E-DBA8-4566-B0D4-CFB9B1AD1DAF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"672579e835779c362d01e7fe230d5186865a1ff9","datavalue":{"value":"6106896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1761500$52F11444-D840-4493-B346-91124A56635C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1761500$F52590B1-8022-45AA-B3B3-2F48DE0EFF27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8593897ec730cdc9f6c027848fb59a2e6f1469f","datavalue":{"value":"coding theorems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1761500$73CA2807-4AFA-48C9-92F2-C99D2F99CDF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc7a3be412dea2ebd3f60996d8f50756cdcb9083","datavalue":{"value":"minimax trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1761500$B0E26FA3-CAE3-4218-910C-93F8D5F1B6D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"647e6e27aca32215c20a6860be046d7e8c222c36","datavalue":{"value":"adaptive coding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1761500$885DEF04-5CAE-430F-9D06-04F74E35D856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45f02b7a5aae8adf9070444815168c76da88e935","datavalue":{"value":"Huffman tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1761500$26F7F67D-8210-4C44-B646-C83D535C97DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3d0dd03f16da32390905de911f34e65dbd6f314","datavalue":{"value":"semi-static prefix coding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1761500$71EF0E6A-2FB3-4BE3-951B-04C6D9D7B3F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e4a5b819171dd0fa8de17b0e5d4491c841626f8","datavalue":{"value":"group testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1761500$F5D48558-43D1-421A-846C-1C9861218E60","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":"Q1761500$437B600B-C768-4ECF-BD74-D5F66CF5DE38","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ec9688acc88ceff474b0985bc0c895810a5d3b90","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2012.07.016","type":"string"},"datatype":"url"},"type":"statement","id":"Q1761500$AD39E5AE-5301-4453-8DFF-8D3907351707","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6934a18a1b1729dddbb12a6efefe4cc2438b5c09","datavalue":{"value":"W2158036127","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1761500$7D9FBE26-C4DB-402A-B570-EB84088286DA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a943cc6bb3757a8163831af7a0601eaf2626d0a","datavalue":{"value":{"entity-type":"item","numeric-id":3792452,"id":"Q3792452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$F7FD5829-3F0F-48B2-94FB-E9CE59AEFDEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a6895403b2ec68a5532c9e0a01e18b56805c593","datavalue":{"value":{"entity-type":"item","numeric-id":3994535,"id":"Q3994535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$1BF8600D-BB93-43E3-A906-75351C30786C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc2e0d2db0a6d299eb21235fc0a97593259b0d3","datavalue":{"value":{"entity-type":"item","numeric-id":1394121,"id":"Q1394121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$BE7320CE-F2A1-4D44-904B-C5BE6C4E5CBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49f9fddd4b1b3c2efaaca298d2e42fba5adfcbaa","datavalue":{"value":{"entity-type":"item","numeric-id":3818256,"id":"Q3818256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$AE3825BB-D1E2-414C-831C-541A46BBD68E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd4bee714280d2a94e93f4db54af42edab860d4","datavalue":{"value":{"entity-type":"item","numeric-id":3715026,"id":"Q3715026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$E4FED7DC-9B58-4358-AEA5-999B3F9D2578","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$E0F8205F-405C-47AD-A16B-44D53F5D87F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763e3905bf47dfe4b400832ecce38198b0d97320","datavalue":{"value":{"entity-type":"item","numeric-id":5490912,"id":"Q5490912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$27D9175F-ECCC-4597-A61C-5EED69CA559F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81c4de9d9c5204c06c2b0a5d308e0f0a6721f94c","datavalue":{"value":{"entity-type":"item","numeric-id":3044335,"id":"Q3044335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$1284EAAC-853D-45BA-9941-3D824AED67E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f84fa011290477e39984d70440ab13c435ebedbf","datavalue":{"value":{"entity-type":"item","numeric-id":3546819,"id":"Q3546819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$E4DB17B0-90C5-45B1-B79B-22CD9C487B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaa4dd7a219672d1daf696254744cff774ec66f2","datavalue":{"value":{"entity-type":"item","numeric-id":4820879,"id":"Q4820879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$BF7BB060-1E93-45BD-82A8-F8C812F907DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40a9e08009a6c0ed16706856008aca18621eb005","datavalue":{"value":{"entity-type":"item","numeric-id":4060381,"id":"Q4060381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$F0894D1E-A98F-4DE6-8479-1A6335BA844D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78d916ad5295b3ce39e43e3ecc78a817343c3c2","datavalue":{"value":{"entity-type":"item","numeric-id":3527212,"id":"Q3527212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$43AC23FA-0387-4F1D-97CA-4B3A27CD376B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aebf61ce81d3621a54b487fe3195073a9afd7871","datavalue":{"value":{"entity-type":"item","numeric-id":5464594,"id":"Q5464594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$7A0DB568-E86A-480E-8BF6-14896A4136FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"704981f725c800376c148adacbef2bf62d4bf9e0","datavalue":{"value":{"entity-type":"item","numeric-id":845979,"id":"Q845979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$B626E39F-1FD0-4E1D-AEDC-7AFC2B3655D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcc5a7a9480725ee5b488b07cadaf0c6f060942a","datavalue":{"value":{"entity-type":"item","numeric-id":3400581,"id":"Q3400581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$2522BDD8-ECEA-4ADB-9BF4-62463719D308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf2ccdb1a26029e4e9136ceaecce6d3b8f41bf83","datavalue":{"value":{"entity-type":"item","numeric-id":3183465,"id":"Q3183465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$9AC3B2FB-BB59-4CBB-964C-C18F6D0F0D67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3fa90bf11e04487b48a872f3c997442fb817587","datavalue":{"value":{"entity-type":"item","numeric-id":4184761,"id":"Q4184761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$EDD611F5-45AC-4D67-A810-FE4423C5C22B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78fd7ba6bfd9204a3ae6f6818152f93c474623a7","datavalue":{"value":{"entity-type":"item","numeric-id":4141107,"id":"Q4141107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$B3DF6DE7-D1AC-432A-8803-36150AC06FCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48270899dabc7227afea778fe27f24091d151ed1","datavalue":{"value":{"entity-type":"item","numeric-id":3030723,"id":"Q3030723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$30FF7C95-1521-4BB3-86A9-DABB32582767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80e1dbec7084a675afce25c49441fb0cdfccefb1","datavalue":{"value":{"entity-type":"item","numeric-id":4199541,"id":"Q4199541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$A9856A2A-AFAC-42E4-BCAC-986313697B8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f51ab68fb93638e8648c08fc21c5c749fc87f3e4","datavalue":{"value":{"entity-type":"item","numeric-id":5510070,"id":"Q5510070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$EF98E266-E74A-45BF-8B53-096E32BF05F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"657cede08906b97f891139f0d07624649366424f","datavalue":{"value":{"entity-type":"item","numeric-id":2391182,"id":"Q2391182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$9B3CC2F4-F0E1-4E8A-81E7-25635F46D0D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"421866de6affe03e8d0267c7f469dc825db6f174","datavalue":{"value":{"entity-type":"item","numeric-id":4111466,"id":"Q4111466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$757CDAB2-C1F5-400C-BA01-B64E052D1BC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cbb31f70ea95c09e877d3266c4b1ca09e1703c3","datavalue":{"value":{"entity-type":"item","numeric-id":3680759,"id":"Q3680759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$4371CFEF-B7E2-4CB3-AB0E-11BF0A388019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd1771d3626bba8183b38e2e08525e8dd98130cb","datavalue":{"value":{"entity-type":"item","numeric-id":919826,"id":"Q919826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$F1BFD065-3A69-43C6-80E9-C203A86B8512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"288ebf127f550deed1676617cd0c45840253419f","datavalue":{"value":{"entity-type":"item","numeric-id":4863980,"id":"Q4863980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$57F4FE5B-32AE-4991-A9DC-7E7053609132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72cfc6aed23fd61a028b668bceaf30de370e3f27","datavalue":{"value":{"entity-type":"item","numeric-id":3745760,"id":"Q3745760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$F2DD30B4-2A00-4457-9366-24DE170F8963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d144846981036f68e4444a55c8122b742dd1d323","datavalue":{"value":{"entity-type":"item","numeric-id":4264494,"id":"Q4264494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$49AD26C9-49DE-47B3-9E92-9A89CE79EA17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2f7daf7b9bca7f21b26e59653c027feb25086c6","datavalue":{"value":{"entity-type":"item","numeric-id":3360787,"id":"Q3360787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$4D4B3E76-6A67-45A8-B692-D6F39C95A4B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a38c6a62c0d07779ccdb57c3d2b2148673115db","datavalue":{"value":{"entity-type":"item","numeric-id":4189199,"id":"Q4189199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$88E27B85-8C37-4956-95C4-19E30078DB32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c124b23e66bda5f6b96b58b4ca724e8f07b76603","datavalue":{"value":{"entity-type":"item","numeric-id":3229522,"id":"Q3229522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$D18B83DC-160E-43E1-B689-6BE36EF4EDCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78f0cf2b8270f6087b7bc3862da42dbac9e1bf1f","datavalue":{"value":{"entity-type":"item","numeric-id":88168,"id":"Q88168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$38B414DF-8888-460E-8664-A1815F3D0BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d1d65bed60765a4af770043fbcf95bed0eaa6a9","datavalue":{"value":{"entity-type":"item","numeric-id":4131006,"id":"Q4131006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$2E8DC29B-7EF7-4FE5-802D-BDDC5A5D0534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dfa0ffef99980dd6150e96ee8f7fb944063ce69","datavalue":{"value":{"entity-type":"item","numeric-id":3778663,"id":"Q3778663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$5416B6D1-B58D-48C8-842A-F2E1066F9616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8687072d562121a4b13ce53a64485e1ab6d9e44d","datavalue":{"value":{"entity-type":"item","numeric-id":3358643,"id":"Q3358643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1761500$41E0D47C-4E18-4C46-9BDC-539110AED837","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2db082878bb8f72c0012c1aff5b639db4ef2a875","datavalue":{"value":"10.1016/J.EJC.2012.07.016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1761500$3AF34350-4520-4149-8882-16EDF37E0271","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b23c7202107824f09a80ad0ae64a5e238cf7cd8","datavalue":{"value":{"entity-type":"item","numeric-id":3651553,"id":"Q3651553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7ffcffeb0f00ecb17037c8a45be808caaea17fb","datavalue":{"value":{"amount":"+0.949094","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$C274D67F-DEF9-4DD9-9A15-AB99D23AA1D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77e0cdff399cfe2cfa64e1b832b044a12a5489d6","datavalue":{"value":{"entity-type":"item","numeric-id":5317596,"id":"Q5317596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4dc55f97c7b4bdb10122019cd6cf3b838050ef6","datavalue":{"value":{"amount":"+0.8454053","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$7CF83F3E-3C92-46A0-A775-E0E4F8D514DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e34376717ccb10e6719a7f734bed905f5b09be82","datavalue":{"value":{"entity-type":"item","numeric-id":3400581,"id":"Q3400581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"febd161749d53be1f905dd235b8d8e2a1acb0e04","datavalue":{"value":{"amount":"+0.84238446","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$DBD9FE6F-3647-402C-8CEB-0AF4A0BD3298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c618c8aa78e0e31833e469d765360fcf3058e9b9","datavalue":{"value":{"entity-type":"item","numeric-id":4928471,"id":"Q4928471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2c3bb11966086a98c9f2c54ccd6444299a66062","datavalue":{"value":{"amount":"+0.82089305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$840AD3E9-9096-43B9-B2C6-E68F65DB8A57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83c6e4322f6f8855e3183b94091585a622050101","datavalue":{"value":{"entity-type":"item","numeric-id":5110926,"id":"Q5110926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8845df9e860d7bfd8939133a59d91c61dfbbb6d5","datavalue":{"value":{"amount":"+0.82007164","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$3F5FBCC7-33A2-4292-B004-3F2421AC2152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"668e0f4becd6fbbfb0f26651d57d1d55460fa705","datavalue":{"value":{"entity-type":"item","numeric-id":5906917,"id":"Q5906917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6a425462055af8531bd82cb9f716cf754950966","datavalue":{"value":{"amount":"+0.8165354","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$DD54DBC5-A3A7-41B2-ADC3-A5753229013B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f3ba88a098b78b7b206875ef2e52d7785407a1b","datavalue":{"value":{"entity-type":"item","numeric-id":2444549,"id":"Q2444549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"724d1ab72f6be5073ff929741b9d92e9d52c7ae2","datavalue":{"value":{"amount":"+0.810714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$74F495AA-4C4A-4562-9EDA-13C62EE7D134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e76e89983f49dd3b61e5343eea6b5b3c4bdadcd","datavalue":{"value":{"entity-type":"item","numeric-id":1567200,"id":"Q1567200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8284f2ccacfd7c60f5ab2366432ba8c1193d3a85","datavalue":{"value":{"amount":"+0.8060951","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$45BD915D-8C22-446C-9445-78FAB80D042F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f98572f3cbe4c1b1eaf3b918b2bda6c5aeb5f5ee","datavalue":{"value":{"entity-type":"item","numeric-id":1283811,"id":"Q1283811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7954d3d802cd5dc4c821ec98cc8e7c724623e687","datavalue":{"value":{"amount":"+0.8032986","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$9609A726-E8E2-43D8-8CBC-2D7DAE62FCEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e0428b381509e849e2de4b47aac585f16dc64b8","datavalue":{"value":{"entity-type":"item","numeric-id":5390280,"id":"Q5390280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0444805050e4ae50f0711839e2370bf394bd04ba","datavalue":{"value":{"amount":"+0.8018712","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1761500$8215E036-3D15-4596-B365-0023B50C50C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimax trees in linear time with applications","badges":[]}}}}}