On the complexity of the embedding problem for hypercube related graphs

DOI10.1016/0166-218X(93)90170-SMaRDI QIDQ1801670zbMATH OpenOpenAlexFDO

Authors A. S. Wagner, Derek G. 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

graph embeddinghypercubemultiprocessorNP-complete

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• Embedding Trees in a Hypercube is NP-Complete
• Fixed hypercube embedding
• The complexity of congestion-1 embedding in a hypercube
• The complexity of cubical graphs
• scientific article; zbMATH DE number 3936535

Cites work

• B-valuations of graphs
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Distance-preserving subgraphs of hypercubes
• Embedding all binary trees in the hypercube
• Embedding Trees in a Hypercube is NP-Complete
• Factoring a graph in polynomial time
• Fixed hypercube embedding
• Generalized Hypercube and Hyperbus Structures for a Computer Network
• scientific article; zbMATH DE number 3833876 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On cubical graphs
• On Factorable Extensions and Subgraphs of Prime Graphs
• Parallel concepts in graph theory
• The complexity of cubical graphs

Cited in

(12)

• A polynomial time approximation scheme for embedding a directed hypergraph on a ring
• Fixed hypercube embedding
• On embedding complete graphs into hypercubes
• On embedding of a hypercube in a completely overlapping network
• The complexity of congestion-1 embedding in a hypercube
• Embedding Trees in a Hypercube is NP-Complete
• The complexity of cubical graphs
• scientific article; zbMATH DE number 3972879 (Why is no real title available?)
• scientific article; zbMATH DE number 614557 (Why is no real title available?)
• Embedding of hypercubes into necklace, windmill and snake graphs
• Weak embeddings of posets to the Boolean lattice
• High-Speed and Noise-Robust Embedding of Hypergraphs Based on Double-Centered Incidence Matrix

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

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