Embedding multidimensional grids into optimal hypercubes

DOI10.1016/J.TCS.2014.07.026zbMath1370.05057arXiv1403.2749OpenAlexW1968417774MaRDI QIDQ740976

Zevi Miller, Dan Pritikin, Ivan Hal 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

hypercubeembeddingdilationgrid

Mathematics Subject Classification ID

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

Cites Work

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

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