Embedding Trees in a Hypercube is NP-Complete

DOI10.1137/0219038zbMath0698.68054OpenAlexW2033562398MaRDI QIDQ3476279

Derek Gordon Corneil, A. S. Wagner

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

hypercubeNP-completemultiprocessorgraph embedding

Mathematics Subject Classification ID

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

Related Items (12)

Spanning multi-paths in hypercubes ⋮ Embedding complete multi-partite graphs into Cartesian product of paths and cycles ⋮ Dense sets and embedding binary trees into hypercubes ⋮ Parity and strong parity edge-colorings of graphs ⋮ Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube ⋮ Hypercube embedding heuristics: An evaluation ⋮ Embedding a subclass of trees into hypercubes ⋮ On the complexity of the embedding problem for hypercube related graphs ⋮ Subgraphs of hypercubes and subdiagrams of Boolean lattices ⋮ 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 ⋮ The number of edges in a subgraph of a Hamming graph

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