Abstract <p>The authors solve the problem of the structural arrangement of embeddings of full rooted binary and ternary trees with <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11968_2025_5152_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\)</EquationSource> <!--CMatCMGU2570004Lozhkin-m1--> </InlineEquation>, <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11968_2025_5152_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="84" /> </InlineMediaObject> <EquationSource Format="TEX">\(k=1,2,\ldots\)</EquationSource> <!--CMatCMGU2570004Lozhkin-m2--> </InlineEquation>, levels into rectangular lattices (RL) with minimal length and close to minimal height. It is assumed that different vertices of the tree go to different (main) vertices of the RL; the leaves of the tree go to the vertices of the RL on its horizontal sides. It is also assumed that the edges of the tree go to simple (transit) chains of RL connecting the images of their end vertices and not going through other main vertices; no more than one (respectively, two) transit chains pass through one and the same edge (one and the same vertex) of the RL.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Some Near-Optimal Embeddings of Full Binary and Ternary Trees in Rectangular Lattices of Minimal Length

  • S. A. Lozhkin,
  • Di Mo

摘要

Abstract

The authors solve the problem of the structural arrangement of embeddings of full rooted binary and ternary trees with \(k\) , \(k=1,2,\ldots\) , levels into rectangular lattices (RL) with minimal length and close to minimal height. It is assumed that different vertices of the tree go to different (main) vertices of the RL; the leaves of the tree go to the vertices of the RL on its horizontal sides. It is also assumed that the edges of the tree go to simple (transit) chains of RL connecting the images of their end vertices and not going through other main vertices; no more than one (respectively, two) transit chains pass through one and the same edge (one and the same vertex) of the RL.