Reductions to Graph Isomorphism

DOI10.1007/978-3-540-77050-3_13zbMath1135.68427OpenAlexW1763617074MaRDI QIDQ5458831

Jacobo Toran

Publication date: 24 April 2008

Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77050-3_13

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)

Cites Work

• Unnamed Item
• Promise problems complete for complexity classes
• On uniform circuit complexity
• Group-theoretic algorithms and graph isomorphism
• 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