Fixed hypercube embedding

DOI10.1016/0020-0190(87)90090-1zbMATH Open0653.68074OpenAlexW1968082675MaRDI QIDQ1108043FDOQ1108043

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

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

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)

Cites Work

• Title not available (Why is that?)
• Distance-preserving subgraphs of hypercubes
• On the complexity of testing a graph for n-cube
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Some Variants of the Bandwidth Minimization Problem
• Title not available (Why is that?)

Cited In (9)

• Multidimensional binary partitions: distributed data structures for spatial partitioning
• Packing the hypercube
• Cover-preserving order embeddings into Boolean lattices
• On embedding complete graphs into hypercubes
• Title not available (Why is that?)
• On the complexity of the embedding problem for hypercube related graphs
• Cover-preserving embeddings of bipartite orders into Boolean lattices
• Embedding Trees in a Hypercube is NP-Complete
• Hypercube embedding heuristics: An evaluation

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)