Fixed hypercube embedding

DOI10.1016/0020-0190(87)90090-1MaRDI QIDQ1108043zbMATHOpenAlexFDO

Authors George Cybenko, David Krumme, K. N. Venkataraman

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90090-1

zbMATH Keywords

hypercubegraph embeddingNP-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Theory of software (68N99)

Recommendations

• On the complexity of the embedding problem for hypercube related graphs
• On embedding complete graphs into hypercubes
• Embedding Trees in a Hypercube is NP-Complete
• The complexity of congestion-1 embedding in a hypercube
• scientific article; zbMATH DE number 1769334

Cites work

• scientific article; zbMATH DE number 3697163 (Why is no real title available?)
• scientific article; zbMATH DE number 3725713 (Why is no real title available?)
• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Distance-preserving subgraphs of hypercubes
• On Some Variants of the Bandwidth Minimization Problem
• On the complexity of testing a graph for n-cube

Cited in

(10)

• Packing the hypercube
• Hypercube embedding heuristics: An evaluation
• On the complexity of the embedding problem for hypercube related graphs
• The hardness of embedding grids and walls
• Embedding Trees in a Hypercube is NP-Complete
• scientific article; zbMATH DE number 718860 (Why is no real title available?)
• On embedding complete graphs into hypercubes
• Multidimensional binary partitions: distributed data structures for spatial partitioning
• Cover-preserving embeddings of bipartite orders into Boolean lattices
• Cover-preserving order embeddings into Boolean lattices

This page was built for publication: Fixed hypercube embedding

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