{"entities":{"Q1854444":{"pageid":1865186,"ns":120,"title":"Item:Q1854444","lastrevid":69361464,"modified":"2026-04-13T06:29:38Z","type":"item","id":"Q1854444","labels":{"en":{"language":"en","value":"Lower bounds for merging networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1853189"}},"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":"Q1854444$2BA042D5-208A-490F-803A-0C2EC8E22A8C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"766746192da63bd7091b461829c3faaed612d798","datavalue":{"value":{"text":"Lower bounds for merging networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1854444$B6CCD891-C8F9-432F-989D-169D4C5F0B11","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"023fd1158b117599be0a2769fc1d9ea3628ab109","datavalue":{"value":"1007.68077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854444$473E27F1-7975-423B-9B90-660B0D0A3746","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"819eac7152d9513d670c824865ff9bc565f3954c","datavalue":{"value":{"entity-type":"item","numeric-id":706628,"id":"Q706628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854444$170E14A0-35C7-46FA-BC2F-C2FAD3769B30","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854444$126171F8-446E-4BEE-ADFA-9FFD1B343161","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6a7e8d599a17c373ba2d71fc88b3043673b9f45a","datavalue":{"value":{"time":"+2003-01-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1854444$3765E2D0-4343-4E88-A742-91D9965D439C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"80651a183122c29dfecafedae591c02acbee8d61","datavalue":{"value":"https://semanticscholar.org/paper/68e314a5699005787aaf4a48afd21090866e395d","type":"string"},"datatype":"url"},"type":"statement","id":"Q1854444$D6BB2B04-2437-4168-9A38-1D166CD0256D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7e20eedab72401b34f682b2928c36ab282feda5b","datavalue":{"value":"A lower bound theorem is established for the number of comparators in a merging network. Let \\(M(m,n)\\) be the least number of comparators required in the \\((m,n)\\)-merging networks, and let \\(C(m,n)\\) be the number of comparators in Batcher's \\((m,n)\\)-merging network, respectively. We prove for \\(n\\geq 1\\) that \\(M(4,n)=C(4,n)\\) for \\(n\\equiv 0,1,3\\bmod 4, M(4,n)\\geq C(4,n)-1\\) for \\(n\\equiv 2\\bmod 4\\), and \\(M(5,n)=C(5,n)\\) for \\(n\\equiv 0,1,5\\bmod 8\\). Furthermore Batcher's \\((6,8k+6)\\)-, \\((7,8k+7)\\)-, and \\((8,8k+8)\\)-merging networks are optimal for \\(k\\geq 0\\). Our lower bound for \\((m,n)\\)-merging networks, \\(m\\leq n\\), has the same terms as \\(C(m,n)\\) has as far as \\(n\\) is concerned. Thus Batcher's \\((m,n)\\)-merging network is optimal up to a constant number of comparators, where the constant depends only on \\(m\\). An open problem posed by \\textit{A. C.-C. Yao} and \\textit{F. F. Yao} [J. Assoc. Comput. Mach. 23, 566-571 (1976; Zbl 0335.68034)] is solved: \\(\\lim_{n\\to\\infty}M(m,n)/n=\\lceil\\log m\\rceil/2+m/2^{\\lceil\\log m\\rceil}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1854444$76F29FE0-14F5-4DD3-811B-69137C278955","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854444$2AB9BE2E-616E-452A-BECD-0B1EC04050A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854444$6E3419EC-A983-4EAE-BF17-BDFB69FDDB27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854444$4A1332BF-B80C-4B75-B04E-8CA8D54FEE6A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0459b8a1585084f95786fbd68ff0be29c1614654","datavalue":{"value":"1853189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854444$FC1CAC9A-2184-42A4-B30D-DAEB4097D54C","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":"Q1854444$CFB2B222-A526-47BE-8A51-82B3C8377DD8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5fcc1b77e53d6273b5b3fb006747ddd4ca0208c8","datavalue":{"value":"W2025099704","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854444$6308BA0D-1B9A-40AA-9646-68200FEAB5C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d52da170739ae909a2b1e1a6a8abb9591ee41347","datavalue":{"value":{"entity-type":"item","numeric-id":1897347,"id":"Q1897347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854444$5FBCD91D-B068-46BF-886E-991A297E1F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854444$E9A6B1D1-19CA-4BF5-A9FB-08489573F8F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57d58a60e523a1b5acfa17a8e1c0cea5e52105b4","datavalue":{"value":{"entity-type":"item","numeric-id":4371518,"id":"Q4371518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854444$571EF404-0833-43F1-A405-AB6948A91FA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8c326eede760cefd8799e27b6a382a854208884","datavalue":{"value":{"entity-type":"item","numeric-id":4102737,"id":"Q4102737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854444$78DA359D-D5E0-4F71-8089-D859437D548A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c072ca92c819dc85405fa7543333b952949691da","datavalue":{"value":"10.1006/INCO.2001.2934","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854444$FAF169A1-BEF0-4E92-9720-3076509765C4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"362f7203d8389f7e8d84bf6733bcbfd74bd3ecd4","datavalue":{"value":{"entity-type":"item","numeric-id":1897347,"id":"Q1897347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f2895100ed2a16d359862002ece03a2833f6ddd","datavalue":{"value":{"amount":"+0.9414266","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$BCB02906-A7BB-437B-A93A-E078597DEF09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11a768a094f81d590de4d0d2074d826576187a0b","datavalue":{"value":{"entity-type":"item","numeric-id":4371518,"id":"Q4371518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02d60f13b462e363bf0b3deacc73821e6fef9479","datavalue":{"value":{"amount":"+0.92301005","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$F702C927-B4AA-4AF3-8167-9DEACFB99218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe8b0d81c57fe21d7ed2744e8542573541020b24","datavalue":{"value":{"entity-type":"item","numeric-id":4230345,"id":"Q4230345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02d60f13b462e363bf0b3deacc73821e6fef9479","datavalue":{"value":{"amount":"+0.92301005","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$0974C475-AD89-4118-81E5-E0486B4F823C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab1efe556edb943c02d1d5eef789420be01964c7","datavalue":{"value":{"entity-type":"item","numeric-id":706629,"id":"Q706629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eca5748ee393b35e4db71a0bba553fec0ad4da07","datavalue":{"value":{"amount":"+0.9174801","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$8816610E-DAE6-4E83-8D00-8D0517A3A907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"262f04ee1ec0eb6c2754485f797d7b30618a5e70","datavalue":{"value":{"entity-type":"item","numeric-id":5431300,"id":"Q5431300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07054e8813ac005b6ffd90e743f227bda8d4939e","datavalue":{"value":{"amount":"+0.9086602","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$50DC8720-0C4F-46D8-8ED9-6ACBE65E68FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdd5ef9d9ee70faaaa60059ff15e5c0706add9ea","datavalue":{"value":{"entity-type":"item","numeric-id":4234092,"id":"Q4234092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"234e7b7ea213a1ed8cfad4164ab345a1a11b60ec","datavalue":{"value":{"amount":"+0.8772243","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$F625EB0C-F595-44C9-B049-8E4252B3085D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6517a3d9010034cce95a25abf59e22745a69f64b","datavalue":{"value":{"entity-type":"item","numeric-id":1095665,"id":"Q1095665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ba0c302a59a2bf71662b73f39dd219eb85cef45","datavalue":{"value":{"amount":"+0.8652142","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$912B21F1-5740-4919-AE70-CDBC0AA7B082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63908de77792093263037499eab72ae89722c1bd","datavalue":{"value":{"entity-type":"item","numeric-id":3387877,"id":"Q3387877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f103e6d3564cc1ddc155d4e6c8040e3052c1d6e","datavalue":{"value":{"amount":"+0.86135846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$68951212-5F4F-4CBB-818F-62E7FA46EE6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6989060be30166be0a4409bfcee42991a30de76b","datavalue":{"value":{"entity-type":"item","numeric-id":4268879,"id":"Q4268879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61b3db8b3633182b2b1feec6ac78aa9f730199d4","datavalue":{"value":{"amount":"+0.86132294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$E42C70A1-DF35-49D0-A5DF-B7D4404B86C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7d901dec084cce3d640005fd07e682022c6e2ba","datavalue":{"value":{"entity-type":"item","numeric-id":4999428,"id":"Q4999428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0fa7b26f076c7223c9d79dc54ac3a431320998b","datavalue":{"value":{"amount":"+0.8593767","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1854444$10CB945B-EE85-4033-B5FF-864B16F67229","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds for merging networks","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_for_merging_networks"}}}}}