Embedding Trees in a Hypercube is NP-Complete

DOI10.1137/0219038MaRDI QIDQ3476279zbMATH OpenOpenAlexFDO

Authors A. S. Wagner, Derek G. Corneil

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219038

zbMATH Keywords

graph embeddinghypercubemultiprocessorNP-complete

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Trees (05C05) Theory of operating systems (68N25) Theory of software (68N99) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of the embedding problem for hypercube related graphs
• Embedding the complete tree in the hypercube
• Fixed hypercube embedding
• The complexity of cubical graphs
• Embedding complete binary trees into hypercubes

Cited in

(15)

• Fixed hypercube embedding
• Finding compact scheme forests in nested normal form is NP-hard
• The number of edges in a subgraph of a Hamming graph
• On the complexity of the embedding problem for hypercube related graphs
• Subgraphs of hypercubes and subdiagrams of Boolean lattices
• Parity and strong parity edge-colorings of graphs
• Spanning multi-paths in hypercubes
• The complexity of cubical graphs
• Embedding complete multi-partite graphs into Cartesian product of paths and cycles
• A METHOD FOR EVALUATING THE EXPECTED LOAD OF DYNAMIC TREE EMBEDDINGS IN HYPERCUBES
• A note on the cubical dimension of new classes of binary trees.
• Embedding a subclass of trees into hypercubes
• Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube
• Dense sets and embedding binary trees into hypercubes
• Hypercube embedding heuristics: An evaluation

This page was built for publication: Embedding Trees in a Hypercube is NP-Complete

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