Homeomorphism of 2-Complexes is Graph Isomorphism Complete

DOI10.1137/S0097539791198900zbMATH Open0818.57002OpenAlexW2013131642MaRDI QIDQ4286232FDOQ4286232

Authors: John Shawe-Taylor, Tomaž Pisanski 

Publication date: 27 March 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539791198900

Recommendations

• HOMEOMORPHISM OF 2-COMPLEXES IS EQUIVALENT TO GRAPH ISOMORPHISM
• scientific article; zbMATH DE number 1186915
• Isomorphisms and homeomorphisms of a class of graphs and spaces
• Complexes of graph homomorphisms
• Homologies of complexes of doubly connected graphs
• scientific article
• The universality of Hom complexes of graphs
• Compactifications of the homeomorphism group of a graph
• Graph homomorphisms with complex values: a dichotomy theorem
• Homomorphisms of 2-edge-colored graphs

zbMATH Keywords

graph isomorphism2- complex homeomorphismcomplexity class of ISOMORPHISM-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Triangulating manifolds (57Q15)

Cited In (6)

• Title not available (Why is that?)
• Drawing graphs by eigenvectors: theory and practice
• Aspects of topology, genus and isomerism in closed 3-valent networks
• HOMEOMORPHISM OF 2-COMPLEXES IS EQUIVALENT TO GRAPH ISOMORPHISM
• Testing homotopy equivalence is isomorphism complete
• On the isomorphism of expressions

This page was built for publication: Homeomorphism of 2-Complexes is Graph Isomorphism Complete

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