The complexity of cubical graphs

DOI10.1016/S0019-9958(85)80012-7MaRDI QIDQ3736911zbMATH OpenFDO

Authors Foto N. Afrati, Christos Papadimitriou, George Papageorgiou

Publication date 1985

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(85)80012-7

zbMATH Keywords

dimensionedge coloringembeddingNP-completesubgraph of a hypercube

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3936535
• Cubical graphs and cubical dimensions
• Embedding Trees in a Hypercube is NP-Complete
• On the complexity of the embedding problem for hypercube related graphs
• The complexity of congestion-1 embedding in a hypercube

Cited in

(15)

• A survey of the theory of hypercube graphs
• Cubical graphs and cubical dimensions
• Recognizing graphs of acyclic cubical complexes
• On the complexity of the embedding problem for hypercube related graphs
• Corrigendum to ``The complexity of cubical graphs
• On semicube graphs
• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• Computing cyclomatic complexity with cubic flowgraphs
• scientific article; zbMATH DE number 5844218 (Why is no real title available?)
• Embedding Trees in a Hypercube is NP-Complete
• scientific article; zbMATH DE number 3936535 (Why is no real title available?)
• scientific article; zbMATH DE number 4010537 (Why is no real title available?)
• scientific article; zbMATH DE number 125454 (Why is no real title available?)
• Boolean autoencoders and hypercube clustering complexity
• Hypercube embedding heuristics: An evaluation

This page was built for publication: The complexity of cubical graphs

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