Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)
Let \(T_h\) be the complete binary tree with \(2^{h+1}-1\) vertices. The (extended) square grid \(M_r\) (\(E_r\)) has vertices \((i,j)\) for \(0 \leq i,j < r\) and two different vertices \((i,j)\) and \((k,l)\) are adjacent iff \(|i-k|+ |j-l|= 1\) (\(|i-k|\leq 1\) and \(|j-l|\leq 1\) in the extended grid). All embeddings considered have total vertex-congestion \(1\), i.e., different vertices of the guest \(T_h\) are mapped to different vertices of the host (\(M_r\) or \(E_r\)) and in case a host-vertex belongs to two paths representing different edges of the guest it is an end-vertex of both paths. If we use the well-known H-tree layout to embed \(T_{h}\) into a square grid, the expansion \(|V(M)|/ |V(T)|\) tends to \(2\) for \(h \to \infty\). The authors give recursive constructions to embed \(T_{2p}\) and \(T_{2p+1}\) into square grids with expansions approaching \(1.606\) and \(1.511\) for \(p \to \infty\). In case of extended grids the expansions approach \(1.234\) and \(1.284\).
- Efficient Embeddings of Binary Trees in VLSI Arrays
- EMBEDDINGS OF COMPLETE BINARY TREES INTO EXTENDED GRIDS WITH EDGE-CONGESTION 1∗
- scientific article; zbMATH DE number 3858396 (Why is no real title available?)
- scientific article; zbMATH DE number 4147467 (Why is no real title available?)
- scientific article; zbMATH DE number 139790 (Why is no real title available?)
- scientific article; zbMATH DE number 219230 (Why is no real title available?)
- Exact wirelength of hypercubes on a grid
- Expansion of layouts of complete binary trees into grids
- 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
- Characterization of the congestion lemma on layout computation
- A linear time algorithm for embedding locally twisted cube into grid network to optimize the layout
- Optimal two-sided embeddings of complete binary trees in rectangular grids
- Conjectures on wirelength of hypercube into cylinder and torus
- Layout of embedding locally twisted cube into the extended theta mesh topology
- Embedding of the folded hypercubes into tori
- Optimal embedding of locally twisted cubes into grids
- Square-root rule of two-dimensional bandwidth problem
- Wirelength of enhanced hypercubes into r-rooted complete binary trees
- Wiener Index of Hypertree
- Embeddings of circulant networks
- scientific article; zbMATH DE number 139790 (Why is no real title available?)
- Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
- Embedding of hypercubes into necklace, windmill and snake graphs
- scientific article; zbMATH DE number 219230 (Why is no real title available?)
- EMBEDDINGS OF COMPLETE BINARY TREES INTO EXTENDED GRIDS WITH EDGE-CONGESTION 1∗
- Bothway embedding of circulant network into grid
- scientific article; zbMATH DE number 1405694 (Why is no real title available?)
- Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees
- Embedding Wheel - like Networks
- Minimum average congestion of enhanced and augmented hypercubes into complete binary trees
- Embedding augmented cube into certain trees and windmill graphs
- Two models of two-dimensional bandwidth problems
- Embedding hypercubes into torus and Cartesian product of paths and/or cycles for minimizing wirelength
- An upper bound for edge congestion and the exact wirelength of embedding onto BC graphs
This page was built for publication: Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962071)
