Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1

DOI10.1016/S0166-218X(99)00161-4zbMath0949.05016OpenAlexW2054681864MaRDI QIDQ1962071

Yanyan Li

Publication date: 29 November 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00161-4

zbMATH Keywords

embeddingscomplete binary treesquare gridextended gridtotal vertex-congestion

Mathematics Subject Classification ID

Trees (05C05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (23)

Wirelength of enhanced hypercubes into \(r\)-rooted complete binary trees ⋮ EMBEDDINGS OF COMPLETE BINARY TREES INTO EXTENDED GRIDS WITH EDGE-CONGESTION 1∗ ⋮ Embeddings of circulant networks ⋮ Layout of embedding locally twisted cube into the extended theta mesh topology ⋮ Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees ⋮ Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength ⋮ Minimum average congestion of enhanced and augmented hypercubes into complete binary trees ⋮ Embedding Wheel - like Networks ⋮ A linear time algorithm for embedding locally twisted cube into grid network to optimize the layout ⋮ Embedding of hypercubes into necklace, windmill and snake graphs ⋮ Optimal Embedding of Locally Twisted Cubes into Grids ⋮ Expansion of layouts of complete binary trees into grids ⋮ Two models of two-dimensional bandwidth problems ⋮ Wiener Index of Hypertree ⋮ Bothway embedding of circulant network into grid ⋮ Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees ⋮ Wirelength of hypercubes into certain trees ⋮ A linear time algorithm for embedding hypercube into cylinder and torus ⋮ Embedding of the folded hypercubes into tori ⋮ Characterization of the congestion lemma on layout computation ⋮ Exact wirelength of hypercubes on a grid ⋮ Square-root rule of two-dimensional bandwidth problem ⋮ Conjectures on wirelength of hypercube into cylinder and torus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient Embeddings of Binary Trees in VLSI Arrays
• EMBEDDINGS OF COMPLETE BINARY TREES INTO EXTENDED GRIDS WITH EDGE-CONGESTION 1∗

This page was built for publication: Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1