Embedding complete ternary trees into hypercubes | Zendy

S.A. Choudum | Zendy; S. Lavanya | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Embedding complete ternary trees into hypercubes

Author(s) -

S.A. Choudum,

S. Lavanya

Publication year - 2008

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1420

Subject(s) - hypercube , embedding , mathematics , combinatorics , ternary operation , discrete mathematics , computer science , artificial intelligence , programming language

We inductively describe an embedding of a complete ternary tree T h of height h into a hypercube Q of dimension at most (1.6)h + 1 with load 1, dilation 2, node congestion 2 and edge congestion 2. This is an improvement over the known embedding of T h into Q. And it is very close to a conjectured embedding of Havel [3] which states that there exists an embedding of T h into its optimal hypercube with load 1 and dilation 2. The optimal hypercube has dimension (log 2 3)h (= (1.585)h) or (log 2 3)h + 1.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research