On the Hardness of Graph Isomorphism
From MaRDI portal
Publication:4651507
DOI10.1137/S009753970241096XzbMath1055.05106OpenAlexW2127563879MaRDI QIDQ4651507
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s009753970241096x
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (18)
On the fixing sets of dihedral groups ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ The parallel complexity of graph canonization under abelian group action ⋮ On the isomorphism of graphs having some eigenvalues of moderate multiplicity ⋮ Measuring distances between complex networks ⋮ Unnamed Item ⋮ Constructing Hard Examples for Graph Isomorphism ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC! ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ Benchmark Graphs for Practical Graph Isomorphism ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Reductions to graph isomorphism ⋮ Reductions to Graph Isomorphism ⋮ Unnamed Item ⋮ Computational complexity of computing a partial solution for the graph automorphism problems ⋮ On the Complexity of Matroid Isomorphism Problems ⋮ On the isomorphism problem for Helly circular-arc graphs
This page was built for publication: On the Hardness of Graph Isomorphism
