On the complexity of the embedding problem for hypercube related graphs

DOI10.1016/0166-218X(93)90170-SzbMath0777.68051OpenAlexW2074222994MaRDI QIDQ1801670

A. S. Wagner, Derek Gordon Corneil

Publication date: 20 December 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90170-s

zbMATH Keywords

hypercubeNP-completemultiprocessorgraph embedding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Factoring a graph in polynomial time
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Fixed hypercube embedding
• On cubical graphs
• Embedding all binary trees in the hypercube
• Parallel concepts in graph theory
• Distance-preserving subgraphs of hypercubes
• Generalized Hypercube and Hyperbus Structures for a Computer Network
• Embedding Trees in a Hypercube is NP-Complete
• The complexity of cubical graphs
• On Factorable Extensions and Subgraphs of Prime Graphs
• $B$-valuations of graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of the embedding problem for hypercube related graphs