Reductions to Graph Isomorphism
From MaRDI portal
Other degrees and reducibilities in computability and recursion theory (03D30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)
Recommendations
Cites work
- A taxonomy of problems with fast parallel algorithms
- Adaptive logspace reducibility and parallel time
- Completeness results for graph isomorphism.
- Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes
- Group-theoretic algorithms and graph isomorphism
- scientific article; zbMATH DE number 477971 (Why is no real title available?)
- On the Decomposability of NC and AC
- On the Hardness of Graph Isomorphism
- On uniform circuit complexity
- On uniformity within \(NC^ 1\)
- Promise problems complete for complexity classes
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
Cited in
(12)- Graph isomorphism is low for PP
- Graph isomorphism is not \(\mathrm{AC}^0\) reducible to group isomorphism
- Graph isomorphism is not \(\mathsf{AC}^{0}\)-reducible to group isomorphism
- Strong isomorphism reductions in complexity theory
- Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
- scientific article; zbMATH DE number 3851045 (Why is no real title available?)
- scientific article; zbMATH DE number 5704228 (Why is no real title available?)
- scientific article; zbMATH DE number 177426 (Why is no real title available?)
- scientific article; zbMATH DE number 512806 (Why is no real title available?)
- On the Hardness of Graph Isomorphism
- On the reduction of Yutsis graphs
- Reductions to graph isomorphism
This page was built for publication: Reductions to Graph Isomorphism
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458831)
