Reductions to graph isomorphism
From MaRDI portal
Publication:987394
Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)
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
- Graph isomorphism is low for PP
- Group-theoretic algorithms and graph isomorphism
- 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
- Space-bounded hierarchies and probabilistic computations
Cited in
(13)- Graph isomorphism is not \(\mathsf{AC}^{0}\)-reducible to group isomorphism
- Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
- Graph isomorphism is not \(\mathrm{AC}^0\) reducible to group isomorphism
- Reductions to Graph Isomorphism
- scientific article; zbMATH DE number 5704228 (Why is no real title available?)
- A method of graph reduction and its applications
- scientific article; zbMATH DE number 3851045 (Why is no real title available?)
- On the reduction of Yutsis graphs
- Graph isomorphism is low for PP
- CNF and DNF succinct graph encodings
- scientific article; zbMATH DE number 177426 (Why is no real title available?)
- The complexity of homomorphism factorization
- On the Hardness of 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 Q987394)
