Reductions to graph isomorphism

DOI10.1007/s00224-008-9159-1zbMath1205.68167OpenAlexW2005365874MaRDI QIDQ987394

Jacobo Toran

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9159-1

zbMATH Keywords

computational complexitygraph isomorphismreducibilities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

CNF and DNF succinct graph encodings ⋮ The complexity of homomorphism factorization

Cites Work

• Space-bounded hierarchies and probabilistic computations
• Promise problems complete for complexity classes
• On uniform circuit complexity
• Group-theoretic algorithms and graph isomorphism
• Graph isomorphism is low for PP
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Completeness results for graph isomorphism.
• Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes
• On uniformity within \(NC^ 1\)
• On the Decomposability of $NC$ and $AC$
• A taxonomy of problems with fast parallel algorithms
• Adaptive logspace reducibility and parallel time
• On the Hardness of Graph Isomorphism

This page was built for publication: Reductions to graph isomorphism