Embedding multidimensional grids into optimal hypercubes

DOI10.1016/J.TCS.2014.07.026zbMATH Open1370.05057OpenAlexW1968417774MaRDI QIDQ740976FDOQ740976

Authors Z. Miller, Dan Pritikin, I. H. Sudborough

Publication date 10 September 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.2749

zbMATH Keywords

gridhypercubeembeddingdilation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Hypergraphs (05C65)

Abstract: Let $G$ and $H$ be graphs, with $|V(H)|geq|V(G)|$, and $f:V(G)ightarrowV(H)$ a one to one map of their vertices. Let $dilation(f)=maxdis{t}_H(f(x),f(y)):xyinE(G)$, where $dis{t}_H(v,w)$ is the distance between vertices $v$ and $w$ of $H$. Now let $B(G,H)$ = $mi{n}_{f}dilation(f)$, over all such maps $f$. The parameter $B(G,H)$ is a generalization of the classic and well studied "bandwidth" of $G$, defined as $B(G,P(n))$, where $P(n)$ is the path on $n$ points and $n=|V(G)|$. Let $[a_{1}imes{a}_{2}imescdotsimes{a}_k]$ be the $k$-dimensional grid graph with integer values $1$ through $a_i$ in the $i$'th coordinate. In this paper, we study $B(G,H)$ in the case when $G=[a_{1}imes{a}_{2}imescdotsimes{a}_k]$ and $H$ is the hypercube $Q_n$ of dimension $n=lceillo{g}_2(|V(G)|)ceil$, the hypercube of smallest dimension having at least as many points as $G$. Our main result is that ${\displaystyle }$B( [a_{1} imes a_{2} imes cdots imes a_{k} ],Q_{n}) le 3k,${\displaystyle }$ provided $a_{i}geq{2}^{22}$ for each $1leilek$. For such $G$, the bound $3k$ improves on the previous best upper bound $4k+O(1)$. Our methods include an application of Knuth's result on two-way rounding and of the existence of spanning regular cyclic caterpillars in the hypercube.

Recommendations

• Embedding of Grids into Optimal Hypercubes
• Compressing grids into small hypercubes
• Embeddings of hypercubes and grids into de Bruijn graphs
• Many to One Embeddings from Grids into Cylinders, Tori, and Hypercubes
• Efficient embeddings of grids into grids

Cites work

• scientific article; zbMATH DE number 4132179 (Why is no real title available?)
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 3478938 (Why is no real title available?)
• $B$-valuations of graphs
• Approximation and Online Algorithms
• Compressing grids into small hypercubes
• Degree-Constrained Network Spanners with Nonconstant Delay
• Discrepancy of set-systems and matrices
• Efficient Embeddings of Trees in Hypercubes
• Embedding grids into hypercubes
• Embedding of Grids into Optimal Hypercubes
• Embedding the polytomic tree into the $n$-cube
• Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults
• Graph separators, with applications
• Integer matrices with constraints on leading partial row and column sums
• Matrix Rounding under the L_p-Discrepancy Measure and Its Application to Digital Halftoning
• Matrix rounding with respect to small submatrices
• Optimal roundings of sequences and matrices
• Routing a permutation in the hypercube by two sets of edge disjoint paths
• Short dominating paths and cycles in the binary hypercube
• Spanning caterpillars of a hypercube
• Spanning regular caterpillars in hypercubes
• The complexity of congestion-1 embedding in a hypercube
• Unbiased Matrix Rounding

Cited in

(7)

• Many to One Embeddings from Grids into Cylinders, Tori, and Hypercubes
• Efficient embeddings of grids into grids
• Optimal embeddings of odd ladders into a hypercube
• On embedding rectangular grids in hypercubes
• Compressing grids into small hypercubes
• Optimal embedding of hypercube into cylinder
• scientific article; zbMATH DE number 4185639 (Why is no real title available?)

This page was built for publication: Embedding multidimensional grids into optimal hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q740976)