Embedding multidimensional grids into optimal hypercubes

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

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

Publication date: 10 September 2014

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

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.

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)

Cites Work

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

Cited In (4)

• Compressing grids into small hypercubes
• Optimal embeddings of odd ladders into a hypercube
• Optimal embedding of hypercube into cylinder
• Efficient embeddings of grids into grids

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)