{"entities":{"Q1920223":{"pageid":1930965,"ns":120,"title":"Item:Q1920223","lastrevid":69468672,"modified":"2026-04-13T07:12:27Z","type":"item","id":"Q1920223","labels":{"en":{"language":"en","value":"An optimal emulator and VLSI layout for complete binary trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 918708"}},"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":"Q1920223$FD2AC2BA-A536-40CE-BDAC-16C136E39713","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7342cca8bf179d70e4c1ec0428b9d202c3ea22ad","datavalue":{"value":{"text":"An optimal emulator and VLSI layout for complete binary trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1920223$DC0E9AF9-3045-4944-A61B-6FC61FC88C4A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f0d2ef1aa56f7832792f83c20cd349bc4c63a77","datavalue":{"value":"0865.68085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920223$09F81065-0CAE-4D16-A1BB-B247C7285445","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9a4fe62e49c4ce0e93cd6245195d9555b09d831","datavalue":{"value":{"entity-type":"item","numeric-id":1920222,"id":"Q1920222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920223$E8D0AD4B-C0B0-41FB-A2EA-CF012D99AD10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9efce19789f6b40b625774ced71ad7d4a9348430","datavalue":{"value":{"entity-type":"item","numeric-id":1266701,"id":"Q1266701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920223$2FF20DF0-411D-4B00-BA44-C05782F1B378","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920223$4A2008A1-B5D0-4B15-85FF-7A24CAAFF3CA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c52e4811fffdb8f318da6437d640586a60136db4","datavalue":{"value":{"time":"+1996-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1920223$6767D216-8AEE-45CF-987A-662BD17EEBA8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7092f49abcd2e39d5fd112af5e40ef4ceedded9c","datavalue":{"value":"How complex does a graph need to be in order to emulate an arbitrary size complete binary tree with the same level of efficiency as would be obtained by a directed complete graph? In this paper, this question is answered by showing that any \\(N= 2^n\\)-node graph needs to have at least \\({{3N-2} \\over 2}\\) edges in order to perform this emulation. Subsequently, a graph is presented which meets this bound, and it is shown how to optimally embed an arbitrary size complete binary tree in the proposed graph. It is also shown how to optimally embed a \\(kN\\) node cycle in the proposed graph of \\(N\\) nodes with unit dilation, unit congestion and uniform load of \\(k\\). Finally optimal VLSI layouts are presented for the proposed graph which require asymptotically same area as the corresponding layouts for complete binary trees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920223$EC5600C2-D3DE-4CAF-BB3C-20A11AD42A8A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920223$E72FB03D-2968-443B-9751-8017A69287EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920223$815A2C25-8F9B-45BD-8D3C-5EFE8C2EC4AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3cb322112ae56aec500b334b7351f32fb107365","datavalue":{"value":"68W35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920223$ECABE889-468F-48C3-B116-6C6452A6EA91","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c78f380d85170f8240a5b557f774d0787a44bb95","datavalue":{"value":"918708","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920223$D9F1BF24-C616-4859-A275-E83A60C0D0BF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"12f70731a6393fafc48cfed4170e869f069a0e76","datavalue":{"value":"parallel architectures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920223$04A4BEA5-CCDF-466E-A56F-FF457EB8A350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22bf57f5dd7fd116d34a1a789bd1bf0b6d51d6a1","datavalue":{"value":"VLSI layout","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920223$35D82193-FEA5-4FB3-AAA0-35351D66C07D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba9992e11c5a892ccd97460fbc31ceefeeb8b95d","datavalue":{"value":"graph embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920223$F448F504-5142-478D-8F29-E5D31A765D98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cfab7320641965853a62ff5e5c00f87e266c99b","datavalue":{"value":"binary trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920223$8BA87884-EC96-4887-8E60-43920AACB105","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":"Q1920223$B403DCA1-40F9-4023-AB96-9AF570A43313","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9f0250719fe110f40d0444da8f86fd972c031568","datavalue":{"value":"https://doi.org/10.1007/s002360050093","type":"string"},"datatype":"url"},"type":"statement","id":"Q1920223$85371F96-AD0D-4C69-95DF-970C734865A7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eebe6ba5617720d63bf915b8ded5c3402cabe4ec","datavalue":{"value":"W1977119748","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920223$B62A3ACF-506C-4F25-BF20-B09C579AF783","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c2b6182bf655ff1c10303b38c9c8a7bc96a68b35","datavalue":{"value":"10.1007/S002360050093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920223$79566934-AB73-44E6-A57B-93EB1097625E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"312b5d9e7ea691c434e2fb02f349d26767a6e855","datavalue":{"value":{"entity-type":"item","numeric-id":3786430,"id":"Q3786430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ef2c9157106f740f2eee5e3e0ad25566f542c05","datavalue":{"value":{"amount":"+0.8114534020423889","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":"Q1920223$3C518F3D-DAFE-4715-8D88-EA1647A7F858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53da5f428a803a3ba467ef3b18e583085de68f9f","datavalue":{"value":{"entity-type":"item","numeric-id":1130317,"id":"Q1130317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46d586ddf367baeb13870e506d7cdf7c88a6da08","datavalue":{"value":{"amount":"+0.7918813228607178","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":"Q1920223$26F1F940-6860-4B0A-80A2-75C311D6EACD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a683d83b57817f77f1f00e85ce12021459aebb1","datavalue":{"value":{"entity-type":"item","numeric-id":4694714,"id":"Q4694714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ea937ca6340cef326b4b50efc6270f2681891a0","datavalue":{"value":{"amount":"+0.7909879088401794","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":"Q1920223$E9AE3077-07FA-4DBA-9E1A-AED356BF87A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6edfd44fd3308514f75d3208b8b287d3d57aeae7","datavalue":{"value":{"entity-type":"item","numeric-id":1099135,"id":"Q1099135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ea937ca6340cef326b4b50efc6270f2681891a0","datavalue":{"value":{"amount":"+0.7909879088401794","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":"Q1920223$3F5A399D-AAA4-4633-B52D-429FA87A673A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a068a382beb96ad79bdc66982810cfd3b65c8872","datavalue":{"value":{"entity-type":"item","numeric-id":1209372,"id":"Q1209372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8823f50613d6f17ddd7ebda1ca254b3ccd0559cf","datavalue":{"value":{"amount":"+0.7900910377502441","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":"Q1920223$3BCD3A2B-496A-49AE-AAB0-41736502CC9E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimal emulator and VLSI layout for complete binary trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_optimal_emulator_and_VLSI_layout_for_complete_binary_trees"}}}}}