On the complexity of the embedding problem for hypercube related graphs (Q1801670)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the complexity of the embedding problem for hypercube related graphs |
scientific article |
Statements
On the complexity of the embedding problem for hypercube related graphs (English)
0 references
20 December 1993
0 references
An important family of graphs is the \(n\)-dimensional hypercube, the graph with \(2^ n\) nodes labelled \(0,1,\dots,2^ n-1\) and an edge joining two nodes whenever their binary representation differs in a single coordinate. The problem of deciding if a given source graph is a partial subgraph of an \(n\)-dimensional cube has recently been shown to be NP- complete. We illustrate a reduction technique used to obtain NP-completeness results for a variety of hypercube related graphs. We consider the subgraph isomorhism problem on two related families of guest graphs, the dilation two hypercubes and generalized hypercubes. We show that the embedding problem for both of these problems is NP-complete.
0 references
multiprocessor
0 references
graph embedding
0 references
hypercube
0 references
NP-complete
0 references